题解：P10687 True Liars

· · 题解

被迫营业讲课于是选了 dsu，这是例题。

csp 初赛 trick 告诉我们题面中的边描述的是同族或者异族关系，不能说明到底是神还是恶魔。

考虑二倍域并查集，每个实际点建一个对应的敌对点，对每个边直接按照关系把两个点对应合并即可。

把每个连通块内的实际点给求出来，然后把互相敌对的两个连通块绑成一对，显然对于每一对连通块都必须选择其中恰好一个块，将其中所有实际点加入答案。

每个连通块对按照实际点数量做个差，直接跑一个背包状物求出组合每个大小的方案数，并且上个 bitset 维护选择方案，类似 AT_abc441_f 的处理就好了。

时间复杂度 O(\frac{n^3}w)。

#include<bits/stdc++.h>
#define N 605
using namespace std;
int fa[N<<1];
int find(int x){
    return x==fa[x]?x:fa[x]=find(fa[x]);
}
int siz[N<<1];
bool use[N<<1];
bitset<605>b[N];
int dp[N];
void solve(int n,int m,int k){
    for(int i=1;i<=n*2;i++)
    fa[i]=i,use[i]=siz[i]=0;
    for(int i=0;i<=n;i++)
    b[i].reset(),dp[i]=0;
    dp[0]=1;
    while(m--){
        int u,v;
        string op;
        cin>>u>>v>>op;
        if(op=="yes")
        fa[find(u)]=find(v),
        fa[find(u+n)]=find(v+n);
        else
        fa[find(u+n)]=find(v),
        fa[find(u)]=find(v+n);
    }
    for(int i=1;i<=n;i++)
    siz[find(i)]++;
    vector<int>ve;
    vector<pair<int,int>>rt;
    for(int i=1;i<=n;i++)
    if(!use[find(i)]){
        int x=siz[find(i)];
        int y=siz[find(i+n)];
        if(x>y)rt.push_back({find(i+n),find(i)});
        else rt.push_back({find(i),find(i+n)});
        if(x>y)swap(x,y);
        k-=x;
        y-=x;
        ve.push_back(y);
        use[find(i)]=1;
        use[find(i+n)]=1;
    }
    if(k<0||k>n){
        puts("no");
        return;
    }
    for(int i=0;i<ve.size();i++)
    for(int j=n-ve[i];j>=0;j--)
    if(dp[j]){
        dp[j+ve[i]]+=dp[j];
        b[j+ve[i]]=b[j];
        b[j+ve[i]][i]=1;
    }
    if(dp[k]!=1){
        puts("no");
        return;
    }
    for(int i=1;i<=n*2;i++)
    use[i]=0;
    for(int i=0;i<rt.size();i++)
    if(b[k][i])use[rt[i].second]=1;
    else use[rt[i].first]=1;
    for(int i=1;i<=n;i++)
    if(use[find(i)])
    cout<<i<<'\n';
    cout<<"end\n";
}
int main(){
    int n,p1,p2;
    while(cin>>n>>p1>>p2&&n&&p1&&p2)
    solve(p1+p2,n,p1);
    return 0;
}
// 小女孩一声悲鸣也没有发出，就这样带著像是装出来的笑容倒在地上，然后，再也没有说一句话。

// 这么多血是从那副小小身躯的哪里流出来的？
// 瓦砾转眼间就被染成了红色。

//「啊……啊啊──」

// 恐惧，逐渐吞噬「菈琪旭」的心灵。
// 孤独，逐渐渗透「菈琪旭」的心灵。

// 她已经不做任何抵抗，任由后悔、怜悯、焦躁，以及一切情感的漩涡，将所剩不多的自我碎片涂抹殆尽。