2-sat HDU 1814

题解来自于：http://www.cnblogs.com/kuangbin/archive/2012/10/05/2712622.html

和平委员会

根据宪法，Byteland民主共和国的公众和平委员会应该在国会中通过立法程序来创立。不幸的是，由于某些党派代表之间的不和睦而使得这件事存在障碍。

此委员会必须满足下列条件：

每个党派都在委员会中恰有1个代表，
如果2个代表彼此厌恶，则他们不能都属于委员会。

每个党在议会中有2个代表。代表从1编号到2n。编号为2i-1和2i的代表属于第I个党派。

任务

写一程序：

从文本文件读入党派的数量和关系不友好的代表对，
计算决定建立和平委员会是否可能，若行，则列出委员会的成员表，
结果写入文本文件。

输入

在文本文件的第一个行有2非负整数n和m。他们各自表示：党派的数量n，1 < =n < =8000和不友好的代表对m，0 <=m <=20000。在下面m行的每行为一对整数a,b，1<=a <b<=2n，中间用单个空格隔开。它们表示代表a,b互相厌恶。

输出

如果委员会不能创立，文本文件中应该包括单词NIE。若能够成立，文本文件SPO.OUT中应该包括n个从区间1到2n选出的整数，按升序写出，每行一个，这些数字为委员会中代表的编号。如果委员会能以多种方法形成，程序可以只写他们的某一个。

样品输入

样品输出

建图的话，列一下真值表以后会发现是这样的：A&B=0，因为两者不能同时为1，所以就是A->!B,B->!A

//看看会不会爆int!数组会不会少了一维！

//取物问题一定要小心先手胜利的条件

#include <bits/stdc++.h>

using namespace std;

#pragma comment(linker,"/STACK:102400000,102400000")

#define LL long long

#define ALL(a) a.begin(), a.end()

#define pb push_back

#define mk make_pair

#define fi first

#define se second

#define haha printf("haha\n")

const int maxn =  + ;

struct TwoSAT{

    int n;

    vector<int> G[maxn * ];

    bool mark[maxn * ];

    int c, s[maxn * ];///c是表示目前dfs到的个数和已经被标记的集合s

    bool dfs(int x){

        if (mark[x ^ ]) return false;

        if (mark[x]) return true;

        mark[x] = true;

        s[c++] = x;

        for (int i = ; i < G[x].size(); i++)

            if (!dfs(G[x][i])) return false;

        return true;

    }

    void init(int n){

        this->n = n;

        for (int i = ; i <  * n; i++) G[i].clear();

        memset(mark, , sizeof(mark));

    }

    ///利用题目条件找到x和y，即假设x1[0] | x2[1] = false;即：x1[0]|!x2[1]=false

    ///那么我们反转该条件：即x1[1]|!x2[0] = true,即两者任意一个成立即为true

    ///那么我们只要交叉建图即可

    void add_edge(int x, int y){

        G[x].push_back(y);

    }

    bool solve(){

        memset(mark, , sizeof(mark));

        for (int i = ; i <  * n; i += ){

            if (!mark[i] && !mark[i + ]){

                c = ;

                if (!dfs(i)){

                    while (c) mark[s[--c]] = false;

                    if (!dfs(i + )) return false;

                }

            }

        }

        return true;

    }

};

TwoSAT tar;

int n, m;

int main(){

    while (scanf("%d%d", &n, &m) == ){

        tar.init(n);

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

            int u, v; scanf("%d%d", &u, &v);

            u--, v--;

            tar.add_edge(u, v ^ );

            tar.add_edge(v, u ^ );

        }

        if(!tar.solve()){

            printf("NIE\n"); continue;

        }

        else {

            for (int i = ; i <  * n; i++){

                if (tar.mark[i]){

                    printf("%d\n", i + );

                }

            }

        }

    }

    return ;

}

巴特西

2-sat HDU 1814

和平委员会

最新文章

热门文章