概述
题目描述
曹是一只爱刷街的老曹，暑假期间，他每天都欢快地在阳光大学的校园里刷街。河蟹看到欢快的曹，感到不爽。河蟹决定封锁阳光大学，不让曹刷街。
阳光大学的校园是一张由N个点构成的无向图，N个点之间由M条道路连接。每只河蟹可以对一个点进行封锁，当某个点被封锁后，与这个点相连的道路就被封锁了，曹就无法在与这些道路上刷街了。非常悲剧的一点是，河蟹是一种不和谐的生物，当两只河蟹封锁了相邻的两个点时，他们会发生冲突。
询问：最少需要多少只河蟹，可以封锁所有道路并且不发生冲突。
输入格式
第一行：两个整数N，M
接下来M行：每行两个整数A，B，表示点A到点B之间有道路相连。
输出格式
仅一行：如果河蟹无法封锁所有道路，则输出“Impossible”，否则输出一个整数，表示最少需要多少只河蟹。
输入输出样例
输入 #1复制
3 3 1 2 1 3 2 3
输出 #1复制
Impossible
输入 #2复制
3 2 1 2 2 3
输出 #2复制
1
说明/提示
【数据规模】
1<=N<=10000，1<=M<=100000，任意两点之间最多有一条道路。
题解
本题实际上是一道二分图的题目。
如果我们把图中U、V两个集合中的所有连线都用河蟹断开，就达到了题目要求。要判断图中的二分图，只需要类似01迷宫进行BFS遍历染色即可。在染色的过程中，如果发现连线的另一个端点未染色，就用和当前端点不同的颜色染色，要是已经染色且和当前节点颜色相同，就说明构成循环圈，不能构成二分图，类似下图的情况。
代码如下：
1 #include <iostream> 2 #include <math.h> 3 #include <stdio.h> 4 #include <algorithm> 5 #include <string.h> 6 7 using namespace std; 8 9 const int MAXN = 100005; 10 int first[MAXN], n, m, en, color[MAXN], f[2], u, v; //f统计不同颜色节点数 11 int front, rear; 12 bool vis[MAXN]; 13 int ans; 14 15 struct edge 16 { 17 int zhongdian, changdu; 18 int next; 19 }; 20 21 edge ed[MAXN]; 22 23 void add_edge(int s, int e, int d) 24 { 25 en++; 26 ed[en].next = first[s]; 27 first[s] = en; 28 ed[en].zhongdian = e; 29 ed[en].changdu = d; 30 } 31 32 struct Node 33 { 34 int x, y; 35 int step; 36 }; 37 Node q[MAXN]; 38 39 int bfs(int a) 40 { 41 Node now, next; 42 now.x = a; 43 vis[a] = 1; 44 color[a] = 1; 45 f[0] = 0; 46 f[1] = 1; 47 front = rear = 0; 48 q[rear] = now; 49 rear++; 50 while(front < rear) 51 { 52 now = q[front++]; 53 for(int i = first[now.x]; i; i = ed[i].next) 54 //first[now]：当前点的第一条边；ed[i].next：下一个访问的点 55 { 56 if(color[ed[i].zhongdian] != -1) 57 { 58 if(color[ed[i].zhongdian] == color[now.x]) 59 { 60 cout << "Impossible" << endl; 61 return -1; 62 } 63 } 64 else 65 { 66 color[ed[i].zhongdian] = (color[now.x] + 1) % 2; 67 q[rear].x = ed[i].zhongdian; 68 rear++; 69 f[color[ed[i].zhongdian]]++; 70 } 71 } 72 } 73 ans += min(f[0], f[1]); 74 } 75 76 int main() 77 { 78 cin >> n >> m; 79 for(int i = 1; i <= n; i++) 80 { 81 color[i] = -1; //初始化 82 } 83 for(int i = 1; i <= m; i++) 84 { 85 cin >> u >> v; 86 add_edge(u, v, 0); 87 add_edge(v, u, 0); 88 } 89 for(int i = 1; i <= n; i++) 90 { 91 if(color[i] == -1) 92 { 93 if(bfs(i) < 0) 94 { 95 return 0; 96 } 97 } 98 } 99 cout << ans << endl; 100 101 return 0; 102 }
代码中的f数组是用来统计黑白两种染色点的个数的，本题所求的最小河蟹数就是两种染色点个数的最小值。
转载于:https://www.cnblogs.com/zealsoft/p/11399061.html
最后
以上就是清秀柠檬为你收集整理的洛谷 P1330 封锁阳光大学题解的全部内容，希望文章能够帮你解决洛谷 P1330 封锁阳光大学题解所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复