洛谷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 }