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

算法：HDU 3062 Party （2-SAT入门学习）2014-01-07 csdn shuangde800Problem 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;}