POJ 1417 True Liars(union-find sets)

Description

N个回答，P1个好人(只说实话)， P2个坏人(只说谎话)

X(回答者) Y(被提及的人) A(yes表示X说Y是好人，no表示X说Y是坏人)

问凭现有条件能否确定P1个好人分别是谁

Analyze

分析得知，yes表示X与Y同类，no表示X与Y异类

可用种类并查集。背包的事，以后有缘再见。

Something about 种类并查集

1. A kind of 带权并查集
2. 把所有种类都并到一个集合里，根据每个点与根节点的关系来判断种类，而非将不同种类并到不同的集合里

带权并查集

权值的更新类似向量的表示

Code

#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 610;

int n, p, q;
int fa[N], val[N];

bool used[N];
int a[N][2];
vector<int>b[N][2];
int dp[N][N / 2];
int pre[N][N / 2];

void init()
{
    for(int i = 0; i <= p + q; ++i)
        fa[i] = i;
    memset(val, 0, sizeof(val));
}

int found(int x)
{
    if(x == fa[x])
        return x;

    int tem = found(fa[x]);
    val[x] += val[ fa[x] ];
    val[x] %= 2;
    return fa[x] = tem;
}

//int found(int x)
//{
//    if(x == fa[x])
//        return x;
//
//    int tem = fa[x];
//    fa[x] = found(fa[x]);
//    val[x] += val[tem];
//    val[x] %= 2;
//    return fa[x];
//}

void unite(int u, int v, int tem)
{
    int uu = found(u);
    int vv = found(v);
    if(uu != vv)
    {
        fa[uu] = vv;
        val[uu] = (-val[u] + val[v] + tem + 2) % 2;
    }
}

int main()
{
    while(~scanf("%d %d %d", &n, &p, &q))
    {
        if(n == 0 && p == 0 && q == 0)
            break;
        init();
        int u, v, tem;
        char s[10];
        while(n--)
        {
            scanf("%d %d %s", &u, &v, s);
            if(s[0] == 'y')
                tem = 0;
            else
                tem = 1;
            unite(u, v, tem);
        }


        for(int i = 0; i < N; ++i)
        {
            b[i][0].clear();
            b[i][1].clear();
            a[i][0]=0;
            a[i][1]=0;
        }
        memset(used, 0,sizeof(used));
        int cnt = 1;
        for(int i = 1; i <= p + q; ++i)
            if(!used[i])
            {
                int tmp = found(i);
                for(int j = i; j <= p + q; ++j)
                    if(found(j)==tmp)
                    {
                        used[j] = 1;
                        b[cnt][ val[j] ].push_back(j);
                        a[cnt][ val[j] ]++;
                    }
                cnt++;
            }
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;
        for(int i = 1; i < cnt; ++i)
        {
            for(int j = p; j >= 0; --j)
            {
                if(j - a[i][0] >= 0 && dp[i - 1][j - a[i][0]])
                {
                    dp[i][j] += dp[i - 1][j - a[i][0]];
                    pre[i][j] = j - a[i][0];
                }
                if(j - a[i][1] >= 0 && dp[i - 1][j - a[i][1]])
                {
                    dp[i][j] += dp[i - 1][j - a[i][1]];
                    pre[i][j] = j - a[i][1];
                }
            }
        }
        if(dp[cnt - 1][p]!=1)
            printf("no\n");
        else
        {
            vector<int>ans;
            ans.clear();
            int t = p;
            for(int i = cnt - 1; i >= 1; --i)
            {
                int tmp = t - pre[i][t];
                if(tmp == a[i][0])
                    for(int j = 0; j < a[i][0]; ++j)
                        ans.push_back(b[i][0][j]);
                else
                    for(int j = 0; j < a[i][1]; ++j)
                        ans.push_back(b[i][1][j]);
                t = pre[i][t];
            }
            sort(ans.begin(), ans.end());
            for(int i = 0; i < ans.size(); i++)
                printf("%d\n",ans[i]);
            printf("end\n");
        }
    }
    return 0;
}