传送门
思路：二分染色。根据题意，要求求出所需要的最少士兵。由于图不一定全部联通，所以要求出每一个联通图的最小士兵，同时 不要忘记独立的交汇口也需要有士兵。
Ac代码
#include<iostream>
#include<vector>
#include<cmath>
#include<cstring>
using namespace std;
vector<int>G[10005];
int g[10005], vis[10005];
int n, m;
int sum;
int c1, c2;
bool dfs(int u, int col)
{
vis[u] = col;
if(col == 0)
c1++;
else c2++;
for(int i = 0; i < G[u].size(); i++)
{
int t = G[u][i];
if(vis[t] == vis[u])
{
return false;
}
else if(vis[t] == -1)
{
if(!dfs(t, !col))
{
return false;
}
}
}
return true;
}
void init(int n)
{
memset(vis, -1, sizeof vis);
memset(g, 0, sizeof g);
for(int i = 0; i < n; i++)
G[i].clear();
}
int main()
{
int T;
cin >> T;
while(T--)
{
cin >> n >> m;
int u, v;
init(n);
for(int i = 1; i <= m; i++)
{
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
g[u] = 1;
g[v] = 1;
}
int flag = 0;
int t = 0;
for(int i = 0; i <= n - 1; i++)
{
c1 = c2 = 0;
if(g[i] && vis[i] == -1)
{
if(!dfs(i, 0))
{
flag = 1;
break;
}
t += c1 > c2 ? c2 : c1;
}
}
int cnt1 = 0, cnt2 = 0, cnt3 = 0;
if(flag)
cout << "-1" << endl;
else
{
for(int i = 0; i <= n - 1; i++)
{
if(vis[i] == -1)
cnt3++;
}
cout << t + cnt3 << endl;
}
}
return 0;
}