P1330 封锁阳光大学 DFS+染色

2018-06-27 09:42:44来源:博客园 阅读 ()

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

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

这个题有意思,如果能想到染色,就会很简单,但若想不到就很麻烦

要想把一条边封锁,就必须且只能占据这条边连接的两个点中的一个,于是,使用两种颜色进行染色,使相邻的两个点的颜色不同,

如果从一个点出发染色,还能再回到这个点,并且染的颜色与第一次染的颜色不同,就意味着无法封锁所有道路

如果可以,所有同一种颜色的位置表示一种河蟹的分布方法,也就是说在图中同时有两种分布方法,我们选择其中染色数少的那一种

如果图不是连通的,那在每一次DFS时,需要重置染色数

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 10005;
 4 vector<int> G[maxn];
 5 int used[maxn];
 6 int col[maxn];
 7 int white,black;
 8 
 9 bool dfs(int t,int color){
10     if(used[t]){
11         if(color == col[t])
12             return true;
13         else
14             return false;
15     }
16     else{
17         used[t] = 1;
18         col[t] = color;
19         if(color)
20             black++;
21         else
22             white++;
23         bool ans = true;
24         for(int i=0;i<G[t].size();++i){
25             ans = dfs(G[t][i],1-color);
26             if(!ans)
27                 break;
28         }
29         return ans;
30     }
31 }
32 
33 int main()
34 {
35     int n,m,sum = 0;
36     cin>>n>>m;
37     for(int i=0;i<m;++i){
38         int a,b;
39         cin>>a>>b;
40         G[a].push_back(b);
41         G[b].push_back(a);
42     }
43     bool ans;
44     for(int i=1;i<=n;++i){
45         white = black = 0;
46         if(!used[i])
47             ans = dfs(i,0);
48         if(!ans)
49             break;
50         sum += min(white,black);
51     }
52     if(!ans)
53         cout<<"Impossible";
54     else
55         cout<<sum;
56     return 0;
57 }

 

标签:

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

上一篇:BZOj1261: [SCOI2006]zh_tree(dp)

下一篇:BZOJ1607: [Usaco2008 Dec]Patting Heads 轻拍牛头(模拟 调和级