简述网站推广方式,房产网签备案查询,wordpress 主题放哪,秦皇岛市建设局网站题目描述 曹是一只爱刷街的老曹#xff0c;暑假期间#xff0c;他每天都欢快地在阳光大学的校园里刷街。河蟹看到欢快的曹#xff0c;感到不爽。河蟹决定封锁阳光大学#xff0c;不让曹刷街。 阳光大学的校园是一张由N个点构成的无向图#xff0c;N个点之间由M条道路连接。… 题目描述 曹是一只爱刷街的老曹暑假期间他每天都欢快地在阳光大学的校园里刷街。河蟹看到欢快的曹感到不爽。河蟹决定封锁阳光大学不让曹刷街。 阳光大学的校园是一张由N个点构成的无向图N个点之间由M条道路连接。每只河蟹可以对一个点进行封锁当某个点被封锁后与这个点相连的道路就被封锁了曹就无法在与这些道路上刷街了。非常悲剧的一点是河蟹是一种不和谐的生物当两只河蟹封锁了相邻的两个点时他们会发生冲突。 询问最少需要多少只河蟹可以封锁所有道路并且不发生冲突。 输入格式 第一行两个整数NM 接下来M行每行两个整数AB表示点A到点B之间有道路相连。 输出格式 仅一行如果河蟹无法封锁所有道路则输出“Impossible”否则输出一个整数表示最少需要多少只河蟹。 输入输出样例 输入 #1复制 3 3
1 2
1 3
2 3输出 #1复制 Impossible输入 #2复制 3 2
1 2
2 3输出 #2复制 1 说明/提示 【数据规模】 1N100001M100000任意两点之间最多有一条道路。 题解 本题实际上是一道二分图的题目。 如果我们把图中U、V两个集合中的所有连线都用河蟹断开就达到了题目要求。要判断图中的二分图只需要类似01迷宫进行BFS遍历染色即可。在染色的过程中如果发现连线的另一个端点未染色就用和当前端点不同的颜色染色要是已经染色且和当前节点颜色相同就说明构成循环圈不能构成二分图类似下图的情况。 代码如下 1 #include iostream2 #include math.h3 #include stdio.h4 #include algorithm5 #include string.h6 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 edge16 {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 Node33 {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 else65 {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
