首页 > 代码库 > UVA11080- Place the Guards(二分图染色)
UVA11080- Place the Guards(二分图染色)
题目链接
题意:放最少的士兵去监视所有的道路, 但士兵不可相邻,符合的话,就输出最少的士兵数,否则输出-1
思路:其实就是二分图染色,即黑白染色,然后选择黑白染色最少的那个颜色累加,但要注意可能有多个连通块,只要有一个连通块不符合的话,就不符合。
代码:
#include <iostream> #include <cstdio> #include <cstring> #include <vector> #include <algorithm> using namespace std; const int MAXN = 205; vector<int> g[MAXN]; int color[MAXN]; int v, e, cur, num; bool bipartite(int u, int &cur, int &num) { num++; if (color[u] == 1) cur++; for (int i = 0; i < g[u].size(); i++) { int v = g[u][i]; if (color[v] == color[u]) return false; if (!color[v]) { color[v] = 3 - color[u]; if (!bipartite(v, cur, num)) return false; } } return true; } int main() { int cas; scanf("%d", &cas); while (cas--) { scanf("%d%d", &v, &e); for (int i = 0; i < v; i++) g[i].clear(); int a, b; for (int i = 0; i < e; i++) { scanf("%d%d", &a, &b); g[a].push_back(b); g[b].push_back(a); } int flag = 1; int ans = 0; memset(color, 0, sizeof(color)); for (int i = 0; i < v; i++) { if (!color[i]) { num = cur = 0; color[i] = 1; if (!bipartite(i, cur, num)) { flag = 0; break; } if (num == 1) ans++; else { ans += min(cur, num - cur); } } } if (flag) printf("%d\n", ans); else printf("-1\n"); } return 0; }
UVA11080- Place the Guards(二分图染色)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。