大家好，又见面了，我是全栈君。
UVA 11080 – Place the Guards
题意：一些城市。之间有道路相连，如今要安放警卫，警卫能看守到当前点周围的边，一条边仅仅能有一个警卫看守，问是否有方案，假设有最少放几个警卫
思路：二分图判定，判定过程记录下白点和黑点个数，小的就是要安放的个数，注意假设是0，那么应该是加1
代码：
#include <cstdio>#include <cstring>#include <vector>using namespace std;const int N = 205;int color[N];vector<int> g[N];int b, w;int bipartite(int u) { if (color[u] == 1) b++; if (color[u] == 2) w++; for (int i = 0; i < g[u].size(); i++) { int v = g[u][i]; if (color[u] == color[v]) return false; if (!color[v]) { color[v] = 3 - color[u]; if (!bipartite(v)) return false; } } return true;}int t, n, m;int solve() { int ans = 0; for (int i = 0; i < n; i++) { if (!color[i]) { color[i] = 1; b = w = 0; if (!bipartite(i)) return -1; ans += max(1, min(b, w)); } } return ans;}int main() { scanf("%d", &t); while (t--) { scanf("%d%d", &n, &m); for (int i = 0; i < n; i++) { g[i].clear(); color[i] = 0; } int u, v; while (m--) { scanf("%d%d", &u, &v); g[u].push_back(v); g[v].push_back(u); } printf("%d\n", solve()); } return 0;}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/116454.html原文链接：https://javaforall.net
