曹是一只爱刷街的老曹，暑假期间，他每天都欢快地在阳光大学的校园里刷街。河蟹看到欢快的曹，感到不爽。河蟹决定封锁阳光大学，不让曹刷街。
阳光大学的校园是一张由N个点构成的无向图，N个点之间由M条道路连接。每只河蟹可以对一个点进行封锁，当某个点被封锁后，与这个点相连的道路就被封锁了，曹就无法在与这些道路上刷街了。非常悲剧的一点是，河蟹是一种不和谐的生物，当两只河蟹封锁了相邻的两个点时，他们会发生冲突。
询问：最少需要多少只河蟹，可以封锁所有道路并且不发生冲突。
输入格式：
第一行：两个整数N，M
接下来M行：每行两个整数A，B，表示点A到点B之间有道路相连。
输出格式：
仅一行：如果河蟹无法封锁所有道路，则输出“Impossible”，否则输出一个整数，表示最少需要多少只河蟹。
【数据规模】
1<=N<=10000，1<=M<=100000，任意两点之间最多有一条道路。
这个题目思路是染黑白色，但真的好难想（看了大佬题解后才恍然大悟），我们画图来理解下
样例1的图
选择封锁任意一个点都是可以的，这里我们选择1
可以看到，1-2和1-3的道路走不了了。但是由于选择了1，那么2,3都不能选了（河蟹会起冲突），因此2-3无法封锁
我们用染色的角度来看，1染成白色（用0表示），那么它连到的所有点都要染成黑色（用1表示），可以发现只有一条边两边的点颜色不同才能保证完成封锁
通过上面的分析可以得出完成封锁的条件
1.任意一条边所连得两个点至少有一个被选择
2.任意一条边两边点的颜色不能相同
染黑白色即可
但是这里还有很重要的一点，这个图，不一定是联通的！！！不一定是联通的！！！不一定是联通的！！！（一开始挂掉的原因）所以我们要开个数组记录一下到过哪些点，确保每一个子图都走到；对于每一个子图，如果能封锁，要取黑色和白色中花费最小的（河蟹放黑色点或者放白色点都是可行的）最后汇总一下所有子图的结果就是答案了；如果不能封锁（发现有相邻两个点的颜色相同），直接输出Impossible，结束程序即可
完整代码
#include<bits/stdc++.h> using namespace std;vector <int> edge[1000010];queue <int> que;int vis[1000010],ans[2],col[1000010];int n,m,ansn,aa,bb,flag;void bfs(int x){ while(!que.empty()) { int tmp=que.front(); que.pop(); vis[tmp]=1; for(int i=0;i<edge[tmp].size();i++) { int nowp=edge[tmp][i]; if(col[nowp]==col[tmp])//如果相邻两个点的颜色一致 { cout<<"Impossible";//输出 exit(0);//走人 } if(!vis[nowp])//不一致 { que.push(nowp); col[nowp]=(col[tmp]+1)%2;//染反色 ans[col[nowp]]++;//对应颜色的花费+1 } } }}int main(){ cin>>n>>m; for(int i=1;i<=m;i++) { cin>>aa>>bb; edge[aa].push_back(bb);//无向图正反都要连 edge[bb].push_back(aa); } memset(col,-1,sizeof(col));//初始化颜色数组 for(int i=1;i<=n;i++) { if(vis[i]!=1) //如果不在之前的子图中 { ans[0]=1; //染白色的花费初始化1 ans[1]=0;//染黑色的为0 col[i]=0;//默认白色开始染 que.push(i); bfs(i);//开始染色 ansn+=min(ans[0],ans[1]);//总花费加上黑白色中花费少的 } } cout<<ansn;//快乐的输出 return 0;}参考大佬@KesdiaelKen@hxn2228的题解
转载于:https://www.cnblogs.com/pcpcppc/p/9513740.html
相关资源：各显卡算力对照表！