大家好,又见面了,我是全栈君。
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;}
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116454.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...