codeforces B. Coach 解题报告

题目链接：http://codeforces.com/problemset/problem/300/B

题目意思：给出n个students（n%3 = 0），编号依次为1～n，接下来有m行，每行有两个数：a和b（1<=a, b <= n），表示号码a的人想和号码b的人一起组队。但最终每一组的人最多只能为3个，至于组里只有2个或根本不成组的人可以通过组队变成3个人。问最后每组是否恰好为3人（包括原来不需要组队和组队后的情况），是则输出每组人的编号，否则输出-1。

一开始做的时候觉得像并查集，后来觉得做起来特别复杂，看了看tutorial，知道哪些情况为输出-1的：

情况1：组里面超过3人情况2：2人组人数 > 1人组的人数（不成组）

根据这样硬用并查集来做，代码量非一般多！！！这就是不会算法的悲剧咯～～～

我的思路：

先用并查集来连边，保证大编号的指向最小编号的。

接着统计一人组，二人组，三人组的人数（分别为c1，c2，c3），以判断结果为-1的两种情况。

最后依次输出：二人组 + 一人组，三人组，一人组（除了三人组的情况其他两种都要组合）

（以后学好dfs一定要写条简短的代码，呜呜呜～～～整个晚上没了）

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstdlib>
  4 #include <cstring>
  5 using namespace std;
  6 
  7 const int maxn = 48 + 5;
  8 int res[maxn], cnt[maxn], vis[maxn], vis1[maxn], vis2[maxn];
  9 
 10 int find(int x)
 11 {
 12     while (x != res[x])
 13         x = res[x];
 14     return x;
 15 }
 16 
 17 void merge(int x, int y)
 18 {
 19     int fx = find(x);
 20     int fy = find(y);
 21     if (fx > fy)
 22         res[fx] = fy;
 23     else
 24         res[fy] = fx;
 25 }
 26 
 27 int main()
 28 {
 29     int n, m, i, j, k, a, b;
 30     while (scanf("%d%d", &n, &m) != EOF)
 31     {
 32         for (i = 1; i <= n; i++)
 33             res[i] = i;
 34         for (i = 0; i < m; i++)
 35         {
 36             scanf("%d%d", &a, &b);
 37             merge(a, b);
 38         }
 39         memset(vis, 0, sizeof(vis));       
 40         memset(vis1, 0, sizeof(vis1));
 41         memset(cnt, 0, sizeof(cnt));
 42         int flag, c2, c1, c3, f;
 43         c1 = c2 = c3 = 0;
 44         for (i = 1; i <= n; i++)
 45         {
 46             flag = 1;
 47             if (res[i] == i)
 48             {
 49                 f = 0;
 50                 for (j = i+1; j <= n; j++)
 51                 {
 52                     if (res[j] == i)
 53                     {
 54                         cnt[i]++;
 55                         f = 1;    // 1 p num 的标记
 56                     }
 57                 }
 58                 if (cnt[i] == 2)  // 3 p num
 59                     c3++;
 60                 if (cnt[i] == 1)  // 2 p num
 61                 {
 62                     c2++;
 63                     vis1[i] = 1;
 64                 }
 65                 if (cnt[i] >= 3)    // 组里的人多于3个
 66                     flag = 0; 
 67                 if (!f)            //  1 p num
 68                 {
 69                     vis[i] = 1;
 70                     c1++;
 71                 }
 72             }
 73             if (!flag)
 74                 break;
 75         }
 76         if (c2 > c1 || !flag)
 77             printf("-1
");
 78         else         
 79         {  
 80             memset(vis2, 0, sizeof(vis2));
 81             for (i = 1; i <= n; i++)     // 2 p num + 1 p num
 82             {
 83                 if (res[i] == i && vis1[i])  // vis1[i] 保证是2 p num
 84                 {
 85                     printf("%d ", i);
 86                     vis2[i] = 1;        // sign used
 87                     for (j = i+1; j <= n; j++)
 88                     {
 89                         if (!vis[j] && res[j] == i)  // !vis[j]：保证先输出2 p num的人
 90                         {
 91                             vis2[j] = 1;
 92                             printf("%d ", j);
 93                             for (k = 1; k <= n; k++)  // 1 p
 94                             {
 95                                 if (res[k] == k && vis[k] && !vis2[k])  // vis[k]:1 p num 的人
 96                                 {
 97                                     printf("%d
", k);
 98                                     vis2[k] = 1;
 99                                     c1--;  // 每输出一次减去一个1 p num的人
100                                     break;
101                                 }
102                             }
103                         }
104                     }
105                 }
106             }
107             for (i = 1; i <= n; i++)     // 3 p num
108             {
109                 if (res[i] == i && !vis1[i] && !vis[i]) // !vis1[i]：保证不是2 p num；!vis[i]：保证不是1 p num
110                 {
111                     for (j = i; j <= n; j++)
112                     {
113                         if (res[j] == i && !vis[j]) 
114                         {
115                             printf("%d ", j);
116                             vis2[j] = 1;
117                         }
118                     }
119                     printf("
");
120                 }
121             }
122             int count = 0;
123             for (i = 1; i <= n && c1; i++)    // 剩下的 1 p num的人，每3个人合成1组
124             {
125                 if (!vis2[i])
126                 {
127                     printf("%d ", i);
128                     c1--;
129                     count++;
130                     if (count % 3 == 0)
131                         printf("
");
132                 }
133             }            
134         }
135     }
136     return 0;
137 }
138