欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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 }