HDUOJ 1814(2-SAT)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1814

题意:大意就是有一个委员会每个党派会派一个且只有一个人去参与,每个党派有两个人选。

序号2i-1和2i属于同一个党派

限制条件:如果两个人互相不喜欢对方 那么就不能同时出现参与委员会。

问委员会是否有可能成立 如果成立按数字序从小到大输出 否则输出NIE

思路:面对这种问题 抽象成N对物品每个物品必须选取一个也只能选取一个即2-SAT模型 如果矛盾就添边 即如果x与y互相不喜欢就添一条x到y^1的边和y到x^1的边表示如果选了x就只能选y所在党派的另一个人 然后跑一下2-SAT模板就好 因为在DFS的时候就是以数字序最小的开始搜索的 所以最后mark数组标记的一定是最小数字序。

#include <bits/stdc++.h>
using namespace std;
const int maxn=8000+5;
struct TwoSAT{
    int n;
    vector<int>G[maxn*2];
    bool mark[maxn*2];
    int S[maxn*2],c;

    bool dfs(int x){
        if (mark[x^1]) return false;
        if (mark[x]) return true;
        mark[x]=true;
        S[c++]=x;
        for (int i=0;i<G[x].size();i++)
            if (!dfs(G[x][i])) return false;
        return true;
    }

    void init(int n){
        this->n=n;
        for (int i=0;i<n*2;i++) G[i].clear();
        memset(mark,false,sizeof(mark));
    }

    void add_clause(int x,int y){
        G[x].push_back(y^1);
        G[y].push_back(x^1);
    }

    bool solve(){
        for (int i=0;i<n*2;i+=2){
            if (!mark[i] && !mark[i+1]){
                c=0;
                if (!dfs(i)){
                    while (c>0) mark[S[--c]]=false;
                    if (!dfs(i+1)) return false;
                }
            }
        }
        return true;
    }
}A;
int n,m;
int main(){
    while (~scanf("%d%d",&n,&m)){
        A.init(n);
        for (int i=1;i<=m;i++){
            int a,b;
            scanf("%d%d",&a,&b);
            a--;
            b--;
            A.add_clause(a,b);
        }
        if (!A.solve()) puts("NIE");
        else{
            for (int i=0;i<n*2;i+=2){
                if (A.mark[i]) printf("%d\n",i+1);
                else printf("%d\n",i+2);
            }
        }
    }

    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注