题解 P5782【 [POI2001] 和平委员会】

P5782 [POI2001] 和平委员会

先导题

• P4782 【模板】2-SAT 问题
• P4171 [JSOI2010] 满汉全席

我的 2-SAT 总结

不会 2-SAT 的同学可以看上面的总结，里面有我入门的学习资料。

有一个 naive 的想法。

直接让厌恶的两个人互相矛盾，最后再让同党两两互相矛盾。

while(m--)
{
    scanf("%d%d",&u,&v);
    add(u,v+n); add(v,u+n);
}
for(int i=1;i<=n;i+=2) {add(i,i+1+n); add(i+1+n,i); add(i+1,i+n); add(i+n,i+1);}

上面的方法当然是可以通过本题的。但是这样占用的空间有点大。

一是点的两倍空间，二是最后同党矛盾的边一下就四条。

我们转化一下题意。如果 A 厌恶 B 的话，因为每一个党都要有人参加委员会，所以如果 A 入选，那么 B 的同党 B^{\prime} 就必须入选。所以直接让矛盾的两个人指向对方的同党即可。

记得开双倍空间。

Code

使用 tarjan 算法求解，联想到 tarjan 求割边，连边的时候运用了异或的性质。

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <cmath>

using namespace std;

const int N=2e4+10;
int tot,idx,fir[N],low[N],dfn[N],scc[N],sc,sta[N],top;
bool in[N];
struct edge {int to,nex;} e[N << 1];
inline void add(int u,int v) {e[++tot]=(edge) {v,fir[u]}; fir[u]=tot; return ;}

void tarjan(int u)
{
    dfn[u]=low[u]=++idx;
    sta[++top]=u; in[u]=true;
    int v;
    for(int i=fir[u];i;i=e[i].nex)
        if(!dfn[v=e[i].to]) {tarjan(v); low[u]=min(low[u],low[v]);}
        else if(in[v]) low[u]=min(low[u],dfn[v]);
    if(low[u] == dfn[u])
    {
        sc++;
        while(top)
        {
            scc[v=sta[top--]]=sc; in[v]=false;
            if(u == v) break ;
        }
    }
    return ;
}

int main()
{
//  freopen("work.in","r",stdin); freopen("work.out","w",stdout);
    int n,m,u,v;
    scanf("%d%d",&n,&m);
    n<<=1;
    while(m--)
    {
        scanf("%d%d",&u,&v);
        add(u-1,(v-1)^1); add(v-1,(u-1)^1);
    }
    for(int i=0;i<n;i++) if(!dfn[i]) tarjan(i);
    bool ans=true;
    for(int i=0;i<n && ans;i++) if(scc[i] == scc[i^1]) {printf("NIE"); ans^=1;}
    if(ans) for(int i=0;i<n;i++) if(scc[i] < scc[i^1]) printf("%d\n",i+1);
//  fclose(stdin); fclose(stdout);
    return 0;
}

Thank\ you\ for\ your\ reading\ !