题目链接：
这个题有意思，如果能想到染色，就会很简单，但若想不到就很麻烦
要想把一条边封锁，就必须且只能占据这条边连接的两个点中的一个，于是，使用两种颜色进行染色，使相邻的两个点的颜色不同，
如果从一个点出发染色，还能再回到这个点，并且染的颜色与第一次染的颜色不同，就意味着无法封锁所有道路
如果可以，所有同一种颜色的位置表示一种河蟹的分布方法，也就是说在图中同时有两种分布方法，我们选择其中染色数少的那一种
如果图不是连通的，那在每一次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 }
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论