http://poj.org/problem?id=1417 题目链接这里
又是一题种类并查集，因为poj崩掉了，我就当ac了； 以下是代码；
#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> using namespace std; int f[1010], relation[1010], type1[1010], type2[1010]; // relation是种类并查集关系， //type1 纪录与根节点的同类，type2纪录另一类 int dp[1010][1010]; int parent[1010]; //存根节点 int vis[1010]; int ans[1010]; int Find(int x) { if(f[x] == x) return x; int tmp = f[x]; f[x] = Find(f[x]); relation[x] = relation[x] ^ relation[tmp]; //种类并查集最神奇的地方就是这个关系， //参考了大佬的代码才写出来，比较玄学，这种两个种类的应该就是这个关系写法 return f[x]; } void Union(int x, int y, int rela) { int rx = Find(x); int ry = Find(y); if(rx != ry) { f[rx] = ry; relation[rx] = relation[x]^relation[y]^rela;//合并根节点，注意关系域的转移 } } int main() { int n, p1, p2; while(scanf("%d%d%d", &n, &p1, &p2) && (p1 + p2 + n)) { for(int i = 1; i <= p1 + p2; i++) { f[i] = i, relation[i] = 0, type1[i] = 0, type2[i] = 0; vis[i] = 0; } memset(dp, 0, sizeof(dp)); for(int i = 0; i < n; i++) { int a, b; char s[8]; scanf("%d%d%s", &a, &b, s); if(s[0] == 'y') Union(a, b, 0);//同类会说yes else Union(a, b, 1); } int cnt = 1; for(int i = 1; i <= p1 + p2; i++) { if(!vis[i]) { int fa = Find(i); for(int j = i; j <= p1 + p2; j++) { if(Find(j) == fa && !vis[j]) { vis[j] = 1; if(relation[j] == 0) type1[cnt]++; else type2[cnt]++; // 找出根结点并且纪录两个种类的数目 } } parent[cnt++] = fa; } } dp[0][0] = 1; //方案数背包，看看是不是只有一种方案能满足凑出p1来，凑p2也可以 for(int i = 1; i < cnt; i++) { int Min = min(type1[i], type2[i]); for(int j = p1; j >= Min; j--) { if(dp[i - 1][j - type1[i]]) { dp[i][j] += dp[i - 1][j - type1[i]]; } if(dp[i - 1][j - type2[i]]) { dp[i][j] += dp[i - 1][j - type2[i]]; } //printf("%d %d %d\n",i, j, dp[i][j]); } } // printf("%d\n", dp[cnt-1][p1]); // printf("cnt %d", cnt); if(dp[cnt-1][p1] != 1) { printf("no\n"); continue; } int num = 0; int lost = p1; // 路径回溯找到节点存起来 for(int i = cnt - 1; i >= 1; i--) { if(dp[i - 1][lost - type1[i]] == 1) { for(int j = 1; j <= p1 + p2; j++) { if(Find(j) == parent[i] && relation[j] == 0) ans[num++] = j; } lost -= type1[i]; } else { for(int j = 1; j <= p1 + p2; j++) if(Find(j) == parent[i] && relation[j] == 1) ans[num++] = j; lost -= type2[i]; } } sort(ans, ans + num); for(int i = 0; i < num; i++) printf("%d\n", ans[i]); printf("end\n"); } return 0; }