HDU 1814 Peaceful Commission(2-SAT:最小字典序)

HDU 1814 Peaceful Commission(2-SAT:最小字典序)

http://acm.hdu.edu.cn/showproblem.php?pid=1814

题意:现在有n个党派,每个党派有2个代表,我们需要从每个党派中选一个代表出来,构成一个n个人的立法委员会.但是可能有一些代表互相讨厌,所以他们不能同时出现在立法委员会中.现在问你是否存在一个合理的方案,且输出所有可能立法委员会的最小字典序结果.

分析:

要输出最小字典序的2-SAT问题,用刘汝佳 训练指南上的方法是最简单的. 这里我们把每个党派看出一个点,从0到n-1. 如果对于a(a从0到2*n-1)代表与b代表不和,那么G[a].push_back(b^1) 且 G[b].push_back(a^1).

AC代码:

#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int maxn= 8000+10;
struct TwoSAT
{
    int n;
    vector<int> G[maxn*2];
    int S[maxn*2], c;
    bool mark[maxn*2];

    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<2*n;i++) G[i].clear();
        memset(mark,0,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<2*n;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;
    }

    void print()
    {
        if(!solve()) printf("NIE\n");
        else
        {
            for(int i=0;i<2*n;i++)if(mark[i])
                printf("%d\n",i+1);
        }
    }
}TS;
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)==2)
    {
        TS.init(n);
        while(m--)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            a--, b--;
            TS.add_clause(a,b);
        }
        TS.print();
    }
    return 0;
}