题目大意：一个无向图游戏中，R和B分别表示两个选手，两个人对图中的边轮流着色，R涂红色，B图蓝色，R优先，B的目标是，所有涂成蓝色的边和边相邻的点，构成一个生成子图，图中包含原图所有点，且连通，R的任务就是阻止B。问：B能否win，是，输出YES，否则，输出NO。
很明显是一道博弈题，我的做法是，首先进行缩点，对于相邻顶点u,v，如果u,v间的边数不小于2，则可以缩点，因为无论R对u,v间的边如何着色，都不可能阻止u,v的连通，缩完点以后，很明显，图中任意两个顶点间最多有一条边，此时，R开始涂色，他可以选取任意一条边涂色，然后递归到B涂色，如果所有的涂色方案中B都胜，则输出0, 否则输出1；对于B的涂色过程，B同样可以选择任意一条边涂色，他的涂色，就相当于缩点，对于(u,v)这条边，他现在为蓝色，他可以将所有其他与u相连的顶点和所有其他与v相邻的顶点连在一起，也就是说，如果另有一边(v,r)，如果对边(v,r)的操作，等同于对(u,r)进行操作，对于(u,p)也一样，所以可以缩点，缩点完，如果只剩下一个点，自然无论如何R如何着色，B必胜，否则再递归到R着色。
能写出这种博弈代码，对我来说是多么的不容易啊，呵呵。。，下面是代码，就是有点长了。。。
代码 1 #include < stdio.h > 2 #include < string .h > 3 int n, m; 4 5 int SUO( int map[ 12 ][ 12 ], int mark[]); 6 int dfsB( int map[ 12 ][ 12 ], int mark[]); 7 int dfsR( int map[ 12 ][ 12 ], int mark[]); 8 9 // 如果map[u][v] >= 2 缩点，并返回图中剩余的点数 10 int SUO( int map[ 12 ][ 12 ], int mark[]){ 11 int flag, i, j, k; 12 flag = 1 ; 13 while (flag){ 14 flag = 0 ; 15 for (i = 0 ; i < n; i ++ ){ 16 if (mark[i]) continue ; 17 for (j = i + 1 ; j < n; j ++ ){ 18 if ( ! mark[j] && map[i][j] >= 2 ){ 19 flag = 1 ; 20 break ; 21 } 22 } 23 if (j < n) break ; 24 } 25 if (flag){ 26 mark[j] = 1 ; 27 for (k = 0 ; k < n; k ++ ){ 28 if ( ! mark[k] && k != i){ 29 map[i][k] += map[j][k]; 30 map[k][i] = map[i][k]; 31 } 32 } 33 } 34 } 35 int cnt = 0 ; 36 for (i = 0 ; i < n; i ++ ){ 37 if ( ! mark[i]) cnt ++ ; 38 } 39 return cnt; 40 } 41 42 // 轮到 player B 图色，返回B的博弈结果，1表示win 43 int dfsB( int map[ 12 ][ 12 ], int mark[]){ 44 int i, j, t; 45 int map1[ 12 ][ 12 ]; 46 int mark1[ 12 ]; 47 for (i = 0 ; i < n; i ++ ){ 48 if (mark[i]) continue ; 49 for (j = 0 ; j < n; j ++ ){ 50 if ( ! mark[j] && map[i][j]){ 51 memcpy(map1, map, sizeof (map)); 52 memcpy(mark1, mark, sizeof (mark)); 53 map1[i][j] = 2 ; 54 if (SUO(map1, mark1) == 1 ) return 1 ; 55 t = dfsR(map1, mark1); 56 if (t == 0 ) return 1 ; 57 } 58 } 59 } 60 return 0 ; 61 } 62 63 // 轮到 player R 图色，返回R的博弈结果，1表示win 64 int dfsR( int map[ 12 ][ 12 ], int mark[]){ 65 int map1[ 12 ][ 12 ]; 66 int mark1[ 12 ]; 67 int i, j, t, flag, cnt; 68 flag = 0 ; 69 for (i = 0 ; i < n; i ++ ){ 70 if (mark[i]) continue ; 71 cnt = 0 ; 72 for (j = 0 ; j < n; j ++ ){ 73 if ( ! mark[j] && map[i][j]){ 74 cnt ++ ; 75 } 76 } 77 if (cnt <= 2 ){ 78 flag = 1 ; 79 break ; 80 } 81 } 82 if (flag) return 1 ; 83 for (i = 0 ; i < n; i ++ ){ 84 if (mark[i]) continue ; 85 for (j = i + 1 ; j < n; j ++ ){ 86 if ( ! mark[j] && map[i][j]){ 87 memcpy(map1, map, sizeof (map)); 88 memcpy(mark1, mark, sizeof (mark1)); 89 map1[i][j] = 0 ; 90 t = dfsB(map1, mark1); 91 if (t == 0 ) return 1 ; 92 } 93 } 94 } 95 return 0 ; 96 } 97 98 int main() 99 { 100 int a, b; 101 int map[ 12 ][ 12 ]; 102 int mark[ 12 ]; 103 while (scanf( " %d%d " , & n, & m) != EOF){ 104 if (n == - 1 && m == - 1 ) break ; 105 memset(map, 0 , sizeof (map)); 106 while (m -- ){ 107 scanf( " %d%d " , & a, & b); 108 if (a != b){ // 如果是自环，可以不考虑 109 map[a][b] += 1 ; 110 map[b][a] += 1 ; 111 } 112 } 113 memset(mark, 0 , sizeof (mark)); 114 if (SUO(map, mark) == 1 ) puts( " YES " ); 115 else { 116 if (dfsR(map, mark)) puts( " NO " ); 117 else puts( " YES " ); 118 } 119 } 120 return 0 ; 121 } 122
加一组测试数据：
4 6
0 10 21 23 03 13 2
正解：YES