True Liars POJ - 1417 点击打开链接
这题时kuangbin大大的并查集专题里面的，解法也是kuangbin大大的解法，但是加上了一点我的理解
题意： 给你p1个好人和p2个坏人，编号为1-p1+p2，然后给你n中操作
x1 x2 no：x1说x2不是好人
x1 x2 yes：x1说x2是好人
在这里好人说的总是对的，坏人说的总是坏的，然后问你最后能不能唯一确定哪些是好人，并输出，否则输出”no“
思路：首先，我们假设x1是好人，并且有 x1 x2 yes 那么，x2一定也是好人，如果有x1 x2 no 那么x2一定是坏人。如果假设x1是坏人，如果有x1 x2 no 那么 x2 一定是好人， 如果有 x1 x2 yes 那么x2也是坏人。也就是说， 只要给出的是yes，那么，x1，x2一定是同一类人，否则，一定不是同一类。（自己推一下其中的关系就会明白）。那么，根据这个关系，我们就可以用带权并查集来做了，令同一类为0，否则为1。但是，只用带权并查集的话，只能分出若干个大的集合，每个大的集合又分成两个小集合，即 好人集合 与 坏人集合。但是，我们并不知道每个大集合中，哪个小集合是好人集合哪个集合是坏人集合。这时，就需要我们用dp来处理了。 从每个大集合里面取一个当作好人集合，判断方案是否唯一 。dp[i][j]表示，前i个大集合有j个好人时的方案的个数，最后，只需判断 对应大集合个数和好人个数时的方案数是否为1即可，不唯一，说明不能确定。
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<vector>
5 #include<algorithm>
6 using namespace std;
7 const int Max=605;
8 int a[Max][2];//a[i][0],a[i][1]表示每个大集合分成两部分的个数即相同和不同
9 vector<int> b[Max][2];//三维，记录大集合，小集合，以及集合里面元素的编号
10 bool used[Max];//记录是否在集合里
11 int dp[Max][Max/2];
12 int pre[Max][Max/2];//记录上一个状态的好人个数
13 struct node
14 {
15 int par,relation;
16 };
17 node p[Max];
18 int n,p1,p2,m;
19 void init()
20 {
21 for(int i=1;i<=m;i++){
22 p[i].par=i;
23 p[i].relation=0;
24 }
25 for(int i=0;i<Max;i++){
26 b[i][0].clear();
27 b[i][1].clear();
28 a[i][0]=0;
29 a[i][1]=0;
30 }
31 }
32 int Find(int x)
33 {
34 if(x==p[x].par)
35 return x;
36 int tmp=p[x].par;
37 p[x].par=Find(tmp);
38 p[x].relation=(p[x].relation+p[tmp].relation)%2;//关系域转换方程
39 return p[x].par;
40 }
41 void unite(int x,int y,int c)
42 {
43 int root1=Find(x);
44 int root2=Find(y);
45 if(root1!=root2){
46 p[root2].par=root1;
47 p[root2].relation=(2-p[x].relation+c+p[y].relation)%2;//关系域转换方程
48 }
49 }
50 int main()
51 {
52 int u,v,w;
53 char str[10];
54 while(~scanf("%d%d%d",&n,&p1,&p2)&&(n+p1+p2)){
55 m=p1+p2;
56 init();
57 for(int i=0;i<n;i++){
58 scanf("%d%d%s",&u,&v,str);
59 if(str[0]=='y')
60 w=0;
61 else
62 w=1;
63 unite(u,v,w);
64 }
65 memset(used,0,sizeof(used));
66 int cnt=1;//记录大集合的个数
67 for(int i=1;i<=m;i++)
68 if(!used[i]){
69 int tmp=Find(i);
70 for(int j=i;j<=m;j++){
71 if(Find(j)==tmp){
72 used[j]=true;
73 b[cnt][p[j].relation].push_back(j);
74 a[cnt][p[j].relation]++;
75 }
76 }
77 cnt++;
78 }
79 memset(dp,0,sizeof(dp));
80 dp[0][0]=1;
81 for(int i=1;i<cnt;i++){//前i个集合里面，如果有j个好人的方案
82 for(int j=p1;j>=0;j--){
83 if(j-a[i][0]>=0 && dp[i-1][j-a[i][0]]){//如果人数足够，并且上一状态有满足方案（即保证可以组成一个合法方案）
84 dp[i][j]+=dp[i-1][j-a[i][0]];
85 pre[i][j]=j-a[i][0];
86 }
87 if(j-a[i][1]>=0 && dp[i-1][j-a[i][1]]){
88 dp[i][j]+=dp[i-1][j-a[i][1]];
89 pre[i][j]=j-a[i][1];
90 }
91
92 }
93 }
94 if(dp[cnt-1][p1]!=1){//如果不唯一，说明方案不唯一
95 printf("no\n");
96 }
97 else{
98 vector<int>ans;
99 ans.clear();
100 int t=p1;
101 for(int i=cnt-1;i>=1;i--){
102 int tmp=t-pre[i][t];//选前i个大集合t个好人时，第i个1大集合里面好人的个数
103 if(tmp==a[i][0]){
104 for(int j=0;j<a[i][0];j++)
105 ans.push_back(b[i][0][j]);
106 }
107 else{
108 for(int j=0;j<a[i][1];j++)
109 ans.push_back(b[i][1][j]);
110 }
111 t=pre[i][t];//选前i个大集合t个好人时，第i-1个1大集合里面好人的个数
112 }
113 sort(ans.begin(),ans.end());//按字典序输出
114 for(int i=0;i<ans.size();i++)
115 printf("%d\n",ans[i]);
116 printf("end\n");
117 }
118 }
119 return 0;
120 }
View Code
