记录编号	593664	评测结果	A
题目名称	[POJ 1417]真正的说谎者	最终得分	100
用户昵称	小金	是否通过	通过
代码语言	C++	运行时间	0.010 s
提交时间	2024-09-06 22:06:24	内存使用	5.29 MiB

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=610;
vector<int> pre,ans;
int dp[maxn][maxn],path[maxn][maxn];
int f[maxn],dis[maxn],cnt[maxn][2];
int q,n1,n2;
int find(int p)
{
    if(f[p]==p) return p;
    int res=find(f[p]);
    dis[p]=(dis[p]+dis[f[p]])%2;
    f[p]=res;
    return res;
}
bool merge(int u,int v,int val)
{
    int fu=find(u),fv=find(v);
    if(fu!=fv)
    {
        f[fv]=fu;
        dis[fv]=(dis[u]+dis[v]+val)%2;
        if(dis[fv])
        {
            cnt[fu][0]+=cnt[fv][1];
            cnt[fu][1]+=cnt[fv][0];
        }
        else
        {
            cnt[fu][0]+=cnt[fv][0];
            cnt[fu][1]+=cnt[fv][1];
        }
        return 1;
    }
    else
    {
        if((dis[u]-dis[v]+2)%2!=val) return 0;
        else return 1;
    }
}
int main()
{
    freopen("trueliars.in","r",stdin);
    freopen("trueliars.out","w",stdout);
    bool res,flag;
    int u,v;
    char ch[10];
    while(scanf("%d%d%d",&q,&n1,&n2)!=EOF)
    {
        if(q==0&&n1==0&&n2==0) break;
        for(int i=1;i<=n1+n2;i++)
        {
            f[i]=i;
            dis[i]=0;
            cnt[i][0]=1;
            cnt[i][1]=0;
        }
        flag=1;
        while(q--)
        {
            scanf("%d%d%s",&u,&v,ch);
            if(!flag) continue;
            if(ch[0]=='y') res=merge(u,v,0);
            else res=merge(u,v,1);
            if(!res) flag=0;
        }
        if(flag)
        {
           pre.clear();
           pre.push_back(0);
           for(int i=1;i<=n1+n2;i++)
           {
               if(f[i]==i) pre.push_back(i);
           }
           memset(dp,0,sizeof(dp));
           dp[0][0]=1;
           for(int i=1;i<=pre.size()-1;i++)
           {
               for(int j=0;j<=n1;j++)
               {
                   if(j-cnt[pre[i]][0]>=0&&dp[i-1][j-cnt[pre[i]][0]]!=0)
                   {
                       dp[i][j]+=dp[i-1][j-cnt[pre[i]][0]];
                       path[i][j]=0;
                   }
                   if(j-cnt[pre[i]][1]>=0&&dp[i-1][j-cnt[pre[i]][1]]!=0)
                   {
                       dp[i][j]+=dp[i-1][j-cnt[pre[i]][1]];
                       path[i][j]=1;
                   }
               }
           }
           if(dp[pre.size()-1][n1]==1)
           {
               ans.clear();
               int j=n1;
               for(int i=pre.size()-1;i>=1;i--)
               {
                   for(int k=1;k<=n1+n2;k++)
                   {
                       if(find(k)==pre[i]&&dis[k]==path[i][j]) ans.push_back(k);
                   }
                   j-=cnt[pre[i]][path[i][j]];
               }
               sort(ans.begin(),ans.end());
               for(int i=0;i<ans.size();i++)
               {
                   printf("%d\n",ans[i]);
               }
               printf("end\n");
           }
           else printf("no\n");
        }
        else printf("no\n");
    } 
    return 0;
}