P1330 *阳光大学 DFS+染色
程序员文章站
2022-03-14 14:23:45
题目链接: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 }