算法：HDU 3062 Party （2-SAT入门学习）

Problem Description

有n对夫妻被邀请参加一个聚会，因为场地的问题，每对夫妻中只有1人可以 列席。在2n 个人中，某些人之间有着很大的矛盾（当然夫妻之间是没有矛盾的），有矛盾的2个人是不会同 时出现在聚会上的。有没有可能会有n 个人同时列席？

Input

n： 表示有n对夫妻被邀请 (n<= 1000) m： 表示有m 对矛盾关系 ( m < (n - 1) * (n -1)) 在接下来的m行中，每行会有4个数字，分别是 A1,A2,C1,C2 A1,A2分别表示是夫妻的编号 C1,C2 表示是妻子还是丈夫 ，0表示妻子 ，1是丈夫夫妻编号从 0 到 n -1 Output

如果存在一种情况 则输出YES 否则输出 NO

Sample Input

2 10 1 1 1

Sample Output

YES

这题只需要判断有没有解法，而不用输出方案。

【代码】

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;  

typedef long long int64;  

const int MAXN = 1010;
const int VN = MAXN*2;
const int EN = VN*VN;
int n, m;  

struct Edge{
    int v, next;
};  

struct Graph{
public:
    void init(){
        size = 0;
        memset(head, -1, sizeof(head));
    }
    void addEdge(int u, int v){
        E[size].v = v;
        E[size].next = head[u];
        head[u] = size++;
    }  

public:
    int head[VN];
    Edge E[EN];  

private:
    int size;   

}g;  

class Tow_Sat{
public:
    bool check(const Graph&g, const int n){
        scc(g, n);
        for(int i=0; i<n; ++i)
            if(belong[i*2] == belong[i*2+1])
                return false;
        return true;  

    }
private:
    int top, bcnt, idx;
    int sta[VN];
    int DFN[VN];
    int low[VN];
    int belong[VN];
    bool inStack[VN];  

    void targan(const Graph&g, const int u){
        int v;
        DFN[u] = low[u] = ++idx;
        sta[top++] = u;
        inStack[u] = true;  

        for(int e=g.head[u]; e!=-1; e=g.E[e].next){
            v = g.E[e].v;
            if(DFN[v] < 0){
                targan(g, v);
                low[u] = min(low[u], low[v]);  

            }else if(inStack[v]){
                low[u] = min(low[u], DFN[v]);  

            }
        }  

        if(DFN[u] == low[u]){
            ++bcnt;
            do{
                v = sta[--top];
                inStack[v] = false;
                belong[v] = bcnt;
            }while(u != v);  

        }
    }  

    void scc(const Graph&g, int n){
        top = bcnt = idx = 0;
        memset(DFN, -1, sizeof(DFN));
        memset(inStack, 0, sizeof(inStack));
        for(int i=0; i<2*n; ++i)
            if(DFN[i] < 0) targan(g, i);
    }  

}sat;  

int main(){
    int a,b,c,d;  

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

        g.init();
        for(int i=0; i<m; ++i){
            scanf("%d%d%d%d", &a,&b,&c,&d);
            g.addEdge(a*2+c, b*2+1-d);
            g.addEdge(b*2+d, a*2+1-c);  

        }
        if(sat.check(g, n)) puts("YES");
        else puts("NO");
    }
    return 0;
}

查看本栏目更多精彩内容：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索算法
， description
， 个人
之间
，以便于您获取更多的相关知识。