题目链接
题意：放最少的士兵去监视所有的道路, 但士兵不可相邻，符合的话，就输出最少的士兵数，否则输出-1
思路：其实就是二分图染色，即黑白染色，然后选择黑白染色最少的那个颜色累加，但要注意可能有多个连通块，只要有一个连通块不符合的话，就不符合。
代码：
#include
#include
#include
#include
#include
using namespace std; const int MAXN = 205; vector
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; }