题解：P10687 True Liars

· · 题解

题目大意

现在有 p1 个天神和 p2 个恶魔，天使说真话，恶魔说假话，共有 n 条信息，第 i 条信息表示问编号为 x_i 的人 y_i 是否是天神，问全部的人中有几个是天神

思路

可以先从条件入手，当 x_i 回答 yes 时，如果 x_i 是神那么 y_i 为神，如果 x_i 是恶魔那么 y_i 也为恶魔；当 x_i 回答 no 时，如果 x_i 是神那么 y_i 为恶魔，如果 x_i 是恶魔那么 y_i 为神。

我们发现 x_i 回答 yes 时 x_i 和 y_i 同族，反之异族，有种并查集得感觉。考虑用带权并查集（扩展域不好写）。

设数组 v 表示节点 i 和根节点的关系，如果 v_i 为 0，表示 i 和根节点同族，反之异族，这样设的好处在于可以用异或来更新 i 的孩子与根节点的关系。

在输入时如果为 yes 那么两点同族，合并时传递一个值，表示是否相同，如果相同那么异或 1，否则异或 0。接着记录每个点所属的集合，每个集合中与根节点同族的节点数量和异族的节点数量。

由于我们确定的只是集合中各点与根的关系，因此并不能判断集合中与根同种的还是不同种的节点是神。所以我们可以进行背包 dp。f[i][j] 表示已经从前 i 个集合中选取了 j 个人当神的方案数，然后看是否能凑出从前 tot 个集合中凑出 p1 个神就好了，由于他让判断接是否唯一，所以只要看 f[tot][p1] 是否等于 1 就好了。

code

#include<bits/stdc++.h>
using namespace std;

const int N = 1e3 + 5;

bool flag = true;

int n,que,angel,demon,f[N][N],bel[N],sm[N][2],fa[N],tot;

//n为总共人数，que为条件数，angel为天神数，demon为恶魔数，f为dp数组，bel为节点所属集合，sm为与根节点的关系，第二维 0为相同，1为不同，fa为并查集数组，tot为集合数量 

bool vis[N][2],v[N];

//vis为第 i 个集合中与根节点相同的点选，还是与根节点不同的点选，v为与根节点得关系，0为同族，1为异族 

int find(int x) {              //查询根节点并更新关系 
    if(fa[x] != x) {
        int fax = fa[x];
        fa[x] = find(fa[x]);
        v[x] = v[x] ^ v[fax];
    }
    return fa[x];
}

void unionn(int x,int y,int t) {   //合并两个集合并重新确定关系 
    int xx = find(x);
    int yy = find(y);
    if(xx == yy) return;
    fa[xx] = yy;
    v[xx] = v[x] ^ v[y] ^ t;
}

void init() {                      //初始化 
    n = angel + demon,tot = 0;
    for(int i = 1;i<=n;i++) bel[i] = v[i] = 0;
    for(int i = 1;i<=n;i++) fa[i] = i;
    for(int i = 1;i<=n;i++) for(int j = 0;j<=1;j++) sm[i][j] = vis[i][j] = 0;
    for(int i = 1;i<=n;i++) for(int j = 1;j<=n;j++) f[i][j] = 0;
}

void solve() {
    cin >> que >> angel >> demon;
    if(que == 0 && angel == 0 && demon == 0) { 
        flag = false;
        return;
    }
    init();
    while(que--) {
        int x,y;
        string op;
        cin >> x >> y >> op;
        if(op == "yes") unionn(x,y,0);            //同族合并 
        else unionn(x,y,1);                       //异族合并 
    }
    for(int i = 1;i<=n;i++) if(find(i) == i) bel[i] = ++tot;        //如果自己为根节点，那么将自己所属的集合编号设为 ++tot (tot为已经存在集合数） 
    for(int i = 1;i<=n;i++) sm[bel[find(i)]][v[i]]++;               //传递 
    f[0][0] = 1;                       //一定要初始化！！！
    for(int i = 1;i<=tot;i++) {
        for(int j = 0;j<=angel;j++) {
            if(j >= sm[i][0]) f[i][j] += f[i-1][j-sm[i][0]];        //如果与根节点同族结点个数能放得下，那么累加方案 
            if(j >= sm[i][1]) f[i][j] += f[i-1][j-sm[i][1]];        //如果与根节点异族结点个数能放得下，那么累加方案 
        }
    }
    if(f[tot][angel] != 1) {         //如果最终的方案数不是 1，那么无解 
        cout << "no\n";
        return;
    }
    for(int i = tot;i>=1;i--) {
        if(f[i-1][angel-sm[i][0]] == 1) {   //f[tot][angel] 是由状态 f[tot-1][angel-cnt[i][0/1]]转来的，又由于 f[tot][angel] == 1，
            angel -= sm[i][0];              //也就是说 f[tot-1][angel-sm[i][0]]和 f[tot-1][angel-sm[i][1]] 中,一定是 一个所存方案书数为 1, 另一个所存方案数为 0,因为只有这样,才能保证 f[tot][angel] 等于 1。 
            vis[i][0] = true;               //如果 f[tot-1][angel-sm[i][0]] == 1,那么说明在集合 i 中我选的是与根节点同族的节点当作神;
        }else {                             //如果 f[tot-1][angel-sm[i][1]] == 1, 那么说明在集合 i 中我选的是与根节点【不同】的节点当作神。 
            angel -= sm[i][1];              //我们只需要用一个 vis[i][0/1] 数组记录,
            vis[i][1] = true;               //记录在集合 i 中我用的是哪个种类。 
        }
    }
    for(int i = 1;i<=n;i++) if(vis[bel[find(i)]][v[i]]) cout << i << '\n';          //每个节点所属的集合是否用的是与这个节点种类相同的节点，是就输出 
    cout << "end\n";             //不要忘了输出end 
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    while(flag) solve();
    return 0;
}

这是本 xxs 的第二篇题解，不喜勿喷