记录编号	562924	评测结果	A
题目名称	[POJ 1417]真正的说谎者	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	0.009 s
提交时间	2021-07-10 10:37:05	内存使用	4.29 MiB

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 605;
int n,p,q;
int pre[maxn],d[maxn];
int s[maxn],tot = 0;
int dp[maxn][maxn],num[maxn][2],dis[maxn][maxn];
bool vis[maxn][2];
int find(int x) {
    if(x == pre[x])return x;
    int root = find(pre[x]);
    d[x] ^= d[pre[x]];
    return pre[x] = root;
}
void work() {
    int m = p + q;
    for(int i = 1;i <= m;++ i) {
        pre[i] = i;
        d[i] = 0;
    }
    for(int i = 1;i <= n;++ i) {
        int x,y;
        char s[3];
        scanf("%d%d%s",&x,&y,s);
        int r1 = find(x),r2 = find(y);
        if(r1 == r2)continue ;
        if(s[0] == 'n') {
            pre[r1] = r2;
            d[r1] = d[x] ^ d[y] ^ 1;
        }
        else {
            pre[r1] = r2;
            d[r1] = d[x] ^ d[y] ^ 0;
        }
    }
    memset(dp , 0 , sizeof(dp));
    memset(s , 0 , sizeof(s));
    memset(num , 0 , sizeof(num));
    memset(dis , 0 , sizeof(dis));
    memset(vis , false , sizeof(vis));
    tot = 0;
    for(int i = 1;i <= m;++ i) {
        int t = find(i);
        if(i == t) {
            s[t] = ++ tot;
        }
    }
    for(int i = 1;i <= m;++ i) {
        ++ num[s[find(i)]][d[i]];
    }
    dp[0][0] = 1;
    for(int i = 1;i <= tot;++ i) {
        for(int j = 0;j <= m;++ j) {
            if(j >= num[i][0]&&dp[i - 1][j - num[i][0]]) {
                dp[i][j] += dp[i - 1][j - num[i][0]];
                dis[i][j] = num[i][0];
            }
            if(j >= num[i][1]&&dp[i - 1][j - num[i][1]]) {
                dp[i][j] += dp[i - 1][j - num[i][1]];
                dis[i][j] = num[i][1];
            }
        }
    }
    if(dp[tot][p] != 1) {
        puts("no");
        return ;
    }
    for(int i = tot,j = p;i&&j;-- i) {
        if(dis[i][j] == num[i][0]) {
            vis[i][0] = true;
        }
        else {
            vis[i][1] = true;
        }
        j -= dis[i][j];
    }
    for(int i = 1;i <= m;++ i) {
        if(vis[s[find(i)]][d[i]]) {
            printf("%d\n",i);
        }
    }
    puts("end");
    return ;
}
int main() {
    freopen("trueliars.in","r",stdin);
    freopen("trueliars.out","w",stdout);
    while(~ scanf("%d%d%d",&n,&p,&q)) {
        if(!n&&!p&&!q)break ;
        work();
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}