洛谷P1330 封锁阳光大学

2019-08-16 07:51:12来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

洛谷P1330 封锁阳光大学

 

题目链接:https://www.luogu.org/problemnew/show/P1330

思路:参考过大佬的思路(这句话是写给那些杠精看的,其他看解析的忽略),第一次用染色思想写题。提取题目的关键:

(1)一条边相连的点只至少有一个被占领。

(2)相邻两个点不能都被占领。

(1) + (2) ——> (3)相邻两个点有且只有一个点要被占领。

染色思想:(2)相邻两个点不能都被占领。那么我们可以把相邻的两个点标记为不同的符号,即可以认为染成不同的颜色。

可以结合题目,我们只需要两种颜色就好,我这里为黑和白。

该题为无向图,可能还不是连通图,题目也没讲是不是连通图(就是所有点都可以连在一起),他可能有很多的子图在学校里,

我们可以用dfs的思想,从一个点出发去染色,因为是无向图,我们可以判断,从一个点出发回到这个点,如果该点已经被染的颜色和dfs回来之后又要被染得颜色相同(参考上面的染色思想),

说明这样染色是正确的,说明这个子图可以被部分染色,慢慢的变为全部可以被染色,再得出答案,基本思路就是这样。

那么我们怎么判断需要最少几个点被占领呢,我们知道,一个子图如果可以全部染色,那么,子图上只有两种颜色,黑色,白色,那我们只要取min(黑,白)就好了,

而且,这里的黑白其实作用是一样的(thinking...),代表占领而已,那么如果有很多的子图,我们可以让每个子图都ans += min(黑,白),

最后我们得到的ans就是最少需要占领的点了,在跑程序中,我们当然需要判断能不能符合(3),即相邻两个点颜色不一样,下面代码会有些解释。


 1 #include <iostream>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <cstdio>
 5 #include <string>
 6 #include <vector>
 7 using namespace std;
 8  
 9 typedef long long LL;
10 #define inf (1LL << 30) - 1
11 #define rep(i,j,k) for(int i = (j); i <= (k); i++)
12 #define rep__(i,j,k) for(int i = (j); i < (k); i++)
13 #define per(i,j,k) for(int i = (j); i >= (k); i--)
14 #define per__(i,j,k) for(int i = (j); i > (k); i--)
15 
16 const int N = 10010;
17 vector<int> G[N];//存边
18 bool vis[N]; //该点有没有被访问过
19 int col[N];//每个点的颜色记录
20 int white,black;//全局的
21 int n,m;
22 int u,v;
23 int ans;
24 
25 void input(){
26     //无向图,两个互相存储
27     rep(i,1,m){
28         cin >> u >> v;
29         G[u].push_back(v);
30         G[v].push_back(u);
31     }
32 }
33 
34 bool dfs(int now,int color){
35     
36     bool ok = true; //标记一下该dfs分支可以成功染色,即可以部分染色
37     
38     if(vis[now]){ //如果回到了这个点,判断该点的颜色是不是和要被染的颜色一样
39         if(col[now] == color) return true;//一样,说明该部分染色成功
40         else return false;//不一样,直接一层层退出dfs
41     }
42     //没被染色
43     else{
44         vis[now] = true;//标记访问
45         col[now] = color;//标记颜色
46         //统计颜色,~(-1) = 0
47         if(~color) ++white; 
48         else ++black;
49 
50         
51         rep__(o,0,(int)G[now].size()){
52             ok = dfs(G[now][o],-color); //判断dfs分支能不能全部染色
53             if(!ok) break;//不能直接一层层退出dfs
54         }
55     }
56 
57     return ok;//返回结果
58 }
59 
60 bool all_blocked(){
61 
62     bool ok = true;//来一个标记,判断每个子图是不是都能被染色
63     int color = -1;//1表示白色,-1表示黑色
64     rep(i,1,n){
65 
66         white = black = 0; //每个子图,需要初始化一下
67         //(!!!!)这里说明下,因为是无向图,那么通过一个点一定可以遍历该连通图的所有的点
68         if(!vis[i]){ //该点是否被访问,如果进入了下面的程序,说明是另一个子图, 上面(!!!!!)说了
69             ok = dfs(i,color); //dfs返回值为bool,true表示该子图可以被全部染色
70             if(!ok) break;//false的话说明不能,直接退出,返回false
71             else ans += min(white,black); //可以的话统计最少需要占领的点数
72         }
73     }
74 
75     return ok;
76 }
77 
78 int main(){
79  
80     ios::sync_with_stdio(false);
81     cin.tie(0);
82 
83     cin >> n >> m;
84     input(); //输入
85 
86     //如果能都被染色,输出答案
87     if(all_blocked()) cout << ans << endl;
88     else cout << "Impossible" << endl;
89 
90     getchar();getchar();
91     return 0;
92 }

 


原文链接:https://www.cnblogs.com/SSummerZzz/p/11219960.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:扫描线——POJ1151

下一篇:NOI2019 退役记