題目大意:
某一島上有p1個只說真話的人(好人),p2個只說謊話的人(壞人),所有人都有一個唯一的編號(1~p1+p2)詢問n次.
詢問格式 a b res:
問a號,b號是否是好人,res可以是yes或者no.
判斷是否能找出所有好人,可以的話輸出好人的編號再加個end,否則輸出no.
題目思路:
當回答是yes:
如果a是好人,那麼b肯定也是好人,反之a是壞人,那麼b也肯定是壞人.
所以回答是yes時,a和b是同一類人. www.2cto.com
當回答是no時,同樣可以證明,a和b不是同一類人.
所以我們可以用並查集把所有可以判斷是否同類的人歸在一個集合.
之後我們就要判斷是否有唯一的一種組合使得有p1個人為好人.
這裡我們可以用到dp,因為這個很像背包.
dp[i][j],表示前i個集合中有j人是好人的組合有幾個.
顯然如果dp[集合數][p1]如果等於1,那麼就是有答案了.
狀態方程也很容易推導的.
代碼:
[cpp]
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <ctype.h>
#include <math.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
#define ls rt<<1
#define rs ls|1
#define lson l,mid,ls
#define rson mid+1,r,rs
#define middle (l+r)>>1
#define eps (1e-8)
#define type int
#define clr_all(x,c) memset(x,c,sizeof(x))
#define clr(x,c,n) memset(x,c,sizeof(x[0])*(n+1))
#define MOD 1000000009
#define INF 0x3f3f3f3f
#define pi acos(-1.0)
#define _max(x,y) (((x)>(y))? (x):(y))
#define _min(x,y) (((x)<(y))? (x):(y))
#define _abs(x) ((x)<0? (-(x)):(x))
#define getmin(x,y) (x= (x<0 || (y)<x)? (y):x)
#define getmax(x,y) (x= ((y)>x)? (y):x)
template <class T> void _swap(T &x,T &y){T t=x;x=y;y=t;}
int TS,cas=1;
const int M=1200+5;
int n,p1,p2;
int fa[M],vis[M],tot,dp[M][M];
vector<int>a[M][2];
int res[M],m,pre;
int find(int x){
return (fa[x]==x)? x:(fa[x]=find(fa[x]));
}
void uni(int x,int y){
fa[find(x)]=find(y);
}
void run(){
int i,j;
for(i=1;i<=2*(p1+p2);i++) fa[i]=i;
char op[11];
while(n--){
scanf("%d%d%s",&i,&j,op);
if(op[0]=='y') uni(i,j),uni(i+p1+p2,j+p1+p2);
else uni(i,j+p1+p2),uni(i+p1+p2,j);
}
bool ok=1;
clr_all(vis,0);
for(i=1;i<=p1+p2;i++){
if(find(i) == find(i+p1+p2)){
puts("no");
return;
}
}
tot=0;
for(i=1;i<=p1+p2;i++) if(!vis[i]){
int f0=find(i),f1=find(i+p1+p2);
++tot;
a[tot][0].clear();
a[tot][1].clear();
for(j=1;j<=p1+p2;j++) if(!vis[j]){
int jf=find(j);
if(jf==f0) a[tot][0].push_back(j),vis[j]=1;
else if(jf==f1) a[tot][1].push_back(j),vis[j]=1;
}
}
for(i=1;i<=tot;i++){
}
clr_all(dp,0);
dp[0][0]=1;
for(i=1;i<=tot;i++){
int sz0=a[i][0].size();
int sz1=a[i][1].size();
for(j=p1;j>=sz0;j--) dp[i][j]+=dp[i-1][j-sz0];
for(j=p1;j>=sz1;j--) dp[i][j]+=dp[i-1][j-sz1];
}
if(dp[tot][p1]==1){
m=0;
pre=p1;
for(i=tot;i>=1;i--){
int sz0=a[i][0].size();
if(dp[i-1][pre-sz0]==1){
pre-=sz0;
for(j=0;j<sz0;j++) res[++m]=a[i][0][j];
continue;
}
int sz1=a[i][1].size();
if(dp[i-1][pre-sz1]==1){
pre-=sz1;
for(j=0;j<sz1;j++) res[++m]=a[i][1][j];
continue;
}
}
sort(res+1,res+m+1);
for(i=1;i<=m;i++) printf("%d\n",res[i]);
puts("end");
}else puts("no");
}
void preSof(){
}
int main(){
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
preSof();
//run();
while(~scanf("%d%d%d",&n,&p1,&p2) && (n||p1||p2)) run();
//for(scanf("%d",&TS);cas<=TS;cas++) run();
return 0;
}
