cogs 313. [POI2001] 和平委员会（2-SAT

http://cogs.pro:8080/cogs/problem/problem.php?pid=pyzQimjkj

题意：有n个集合，每个集合有俩元素，要从n个中各选一个放一堆，但是有的俩不能同时取，让你找出一种选取方案。

思路：2-SAT板子，主要学一下这个算法。算法流程：

构图：若a,b不能同时选，连a->b'和b->a'

求图的极大强连通子图：直接tarjan。

缩点然后变成个新的DAG：因为一个强连通分量里选一个其他都要选，一个不选其他都不能选，所以直接缩成一个点。

对新图拓排：要存反边，这个一开始不造为啥，后来看解释是因为传递的是不选择标记，这边往前代走，对面那边往后代走（对这个起作用）。。选一个他后代都得选，不选谁谁的前代都不能选，so...

自底向上进行选择，删除。

输出。

#include<bits/stdc++.h>

#define oth(x) x&1?x+1:x-1

using namespace std;

const int N = 20010;

struct Edge{

    int to,nxt;

}e[50010];

int head[N],dfn[N],low[N],st[N],bel[N];

bool vis[N];

int ru[N],q[N],opp[N],pr[N];

int tot_edge,n,nn,m,tot_node,top,cnt_block,L,R;

vector<int>mp[N];

inline int read() {

    int x = 0,f = 1;char ch = getchar();

    for (; ch<'0'||ch>'9'; ch=getchar()) if(ch=='-') f=-1;

    for (; ch>='0'&&ch<='9'; ch=getchar()) x=x*10+ch-'0';

    return x * f;

}

void add_edge(int u,int v){

    e[++tot_edge].to = v;

    e[tot_edge].nxt = head[u];

    head[u] = tot_edge;

}

void tarjan(int u){

    dfn[u] = low[u] = ++tot_node;

    st[++top] = u;

    vis[u] = true;

    for(int i=head[u];i;i=e[i].nxt){

        int v = e[i].to;

        if(!dfn[v]){

            tarjan(v);

            low[u] = min(low[v],low[u]);

        }

        else if(vis[v])

            low[u] = min(dfn[v],low[u]);

    }

    if(low[u]==dfn[u]){

        ++cnt_block;

        do{

            vis[st[top]] = false;

            bel[st[top]] = cnt_block;

            top--;

        }while(st[top+1]!=u);

    }

}

void topsort(){

    L=1;R=0;

    for(int i=1;i<=cnt_block;i++){

        if(ru[i]==0) q[++R] = i;

    }

    while(L<=R){

        int u = q[L++];

        if(pr[u]) continue;

        pr[u] = 1;pr[opp[u]] = 2;

        int sz = mp[u].size();

        for(int i=0;i<sz;i++){

            int v = mp[u][i];

            ru[v]--;

            if(ru[v]==0) q[++R] = v;

        }

    }

}

bool work(){

    for(int i=1;i<=nn;i++){

        if(!dfn[i]) tarjan(i);

    }

    for(int i=1;i<=nn;i++){

        if(bel[i]==bel[oth(i)]) return false;

        opp[bel[i]] = bel[oth(i)];

        opp[bel[oth(i)]] = bel[i];

    }

    for(int u=1;u<=nn;u++){

        for(int i=head[u];i;i=e[i].nxt){

            int v = e[i].to;

            if(bel[u]!=bel[v]){

                ru[bel[u]]++;

                mp[bel[v]].push_back(bel[u]);

            }

        }

    }

    topsort();

    return true;

}

int main(){

    freopen("spo.in","r",stdin);

    freopen("spo.out","w",stdout);

    n = read(),m = read(),nn = n<<1;

    for(int i=1;i<=m;i++){

        int a = read(),b = read();

        add_edge(a,oth(b));

        add_edge(b,oth(a));

    }

    if(work()){

        for(int i=1;i<=nn;i++){

            if(pr[bel[i]]==1) cout<<i<<endl;

        }

    }

    else puts("NIE");

    return 0;

}

巴特西

cogs 313. [POI2001] 和平委员会（2-SAT

最新文章

热门文章