题意：一个国王要派若干士兵看守王国。王国是一张无向图，然后士兵只能站在点上。每个士兵的看守范围是临近的点与边，士兵看管的的边不能重复。问最少用多少个士兵能使每个点和边都有人看守。
思路：这道题可以抽象成二分图，只要一张图满足二分图。结点数少的颜色的和即为最小的士兵数。
代码如下：
1 /************************************************** 2 * Author : xiaohao Z 3 * Blog : http://www.cnblogs.com/shu-xiaohao/ 4 * Last modified : 2014-01-28 08:40 5 * Filename : uva_11080.cpp 6 * Description : 二分图染色 7 * ************************************************/ 8 9 #include <iostream> 10 #include <cstdio> 11 #include <cstring> 12 #include <cstdlib> 13 #include <cmath> 14 #include <algorithm> 15 #include <queue> 16 #include <stack> 17 #include <vector> 18 #include <set> 19 #include <map> 20 #define MP(a, b) make_pair(a, b) 21 #define PB(a) push_back(a) 22 23 using namespace std; 24 typedef long long ll; 25 typedef pair<int, int> pii; 26 typedef pair<unsigned int,unsigned int> puu; 27 typedef pair<int, double> pid; 28 typedef pair<ll, int> pli; 29 typedef pair<int, ll> pil; 30 31 const int INF = 0x3f3f3f3f; 32 const double eps = 1E-6; 33 const int LEN = 501; 34 int n, m, vis[LEN]; 35 vector<int> Map[LEN]; 36 37 bool dfs(int v, int col){ 38 vis[v] = col; 39 for(int i=0; i<Map[v].size(); i++){ 40 if(vis[Map[v][i]] == 0) {if(!dfs(Map[v][i], -col))return false;} 41 else if(vis[Map[v][i]] == col) return false; 42 } 43 return true; 44 } 45 46 int main() 47 { 48 // freopen("in.txt", "r", stdin); 49 50 int T, a, b; 51 scanf("%d", &T); 52 while(T--){ 53 scanf("%d%d", &n, &m); 54 for(int i=0; i<LEN; i++)Map[i].clear(); 55 memset(vis, 0, sizeof vis); 56 for(int i=0; i<m; i++){ 57 scanf("%d%d", &a, &b); 58 Map[a].PB(b); 59 Map[b].PB(a); 60 } 61 int ans = 0, col = 0; 62 for(int i=0; i<n; i++) 63 if(vis[i] == 0){ 64 if(dfs(i, ++col)==false){ 65 ans = -1; 66 break; 67 } 68 int cnt = 0, rcnt = 0; 69 for(int i=0; i<n; i++){ 70 if(vis[i]==col)cnt++; 71 if(vis[i]==-col)rcnt++; 72 } 73 ans += max(1, min(cnt, rcnt)); 74 } 75 if(ans<0)printf("-1\n"); 76 else printf("%d\n", ans); 77 } 78 return 0; 79 }