题目链接:http://codeforces.com/problemset/problem/357/B
题目意思:输入n个人和m场舞蹈,给出每场舞蹈(只有3个人参与)中参与的舞者的编号,你需要为这些舞者安排衣服的颜色,使得每场舞蹈中3个舞者的颜色都满足是白,红,绿的条件。
特别要注意题目中的两句话:if some dance has two or more dancers from a previous dance, then the current dance stops being spectacular. 和 each dance has at most one dancer who has danced in some previous dance 。也就是说,每一场舞蹈最多只可能有一个旧舞者!
思路其实不难,对于某场舞蹈三个都是新舞者分配颜色就任意;而存在一个旧舞者的话,就要为其余的两个新舞者分配不同于旧舞者的颜色。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 using namespace std; 6 7 const int maxn = 1e5 + 10; 8 9 int dan[maxn]; 10 int visit[maxn]; 11 int t[5]; 12 13 int main() 14 { 15 int m, n, i, j, k, l, t1, t2, t3, temp; 16 while (scanf("%d%d", &n, &m) != EOF) 17 { 18 memset(visit, 0, sizeof(visit)); 19 memset(dan, 0, sizeof(dan)); 20 while (m--) 21 { 22 scanf("%d%d%d", &t1, &t2, &t3); 23 int judge = (visit[t1] == 1) + (visit[t2] == 1) + (visit[t3] == 1); // 判断是否存在旧舞者,0代表没有 24 if (!judge) // 该轮全部为新舞者,依次编号1, 2, 3 25 { 26 dan[t1] = 1; 27 dan[t2] = 2; 28 dan[t3] = 3; 29 visit[t1] = visit[t2] = visit[t3] = 1; 30 } 31 else 32 { 33 t[1] = t1; 34 t[2] = t2; 35 t[3] = t3; 36 for (i = 1; i <= 3; i++) // 判断哪一个是旧舞者 37 { 38 if (visit[t[i]]) 39 { 40 temp = i; // 记住旧舞者在数组t中的编号,以便后面的处理 41 break; 42 } 43 } 44 for (i = 1; i <= 3; i++) 45 { 46 if (i != temp) // 不是旧舞者的第一个新舞者的编号 47 { 48 for (j = 1; j <= 3; j++) // 分配颜色 49 { 50 if (j != dan[t[temp]]) // 第一个新舞者颜色不能跟旧舞者相同 51 { 52 dan[t[i]] = j; 53 visit[t[i]] = 1; 54 for (k = 1; k <= 3; k++) 55 { 56 if (k != i && k != temp) // 第二个新舞者的编号 57 { 58 for (l = 1; l <= 3; l++) 59 { 60 if (l != dan[t[temp]] && l != dan[t[i]]) // 第二个新舞者的颜色不允许与第一个新舞者和旧舞者的颜色相同 61 { 62 dan[t[k]] = l; 63 visit[t[k]] = 1; 64 goto h; // 找到一组解,跳出循环 65 } 66 } 67 } 68 } 69 } 70 } 71 } 72 } 73 } 74 h: ; 75 } 76 for (i = 1; i <= n; i++) 77 { 78 printf("%d ", dan[i]); 79 } 80 printf(" "); 81 } 82 return 0; 83 }