摘要：
有n对夫妇被邀请参加聚会。由于场地问题，只有一对夫妇可以参加。在这20万人中，有些人之间有很大的矛盾。两个矛盾的人不会同时出现在聚会上。），（好。用C将第二个代码更改为312MS++
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
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
否则输出 NO
思路：2-SAT模版题，分别要求夫妻必上一个、仇人不能同时上
两个代码，第一个是普通的搜索，第二个是tarjan的解法，第一个593MS，第二个625MS（难道写挫了。。。？），（好吧用改一下第二个代码用C++交变成了312MS……）
1 #include <cstdio> 2 #include <cstring> 3 using namespacestd; 4 5 const int MAXN = 4010; 6 const int MAXM = 1010*1010*3; 7 8 structTwoSAT{ 9 intn, ecnt; 10 boolmark[MAXN]; 11 int St[MAXN], c;//手动栈 12 inthead[MAXN]; 13 intnext[MAXM], to[MAXM]; 14 15 bool dfs(intx){ 16 if(mark[x^1]) return false; 17 if(mark[x]) return true; 18 mark[x] = true; 19 St[c++] =x; 20 for(int p = head[x]; p; p =next[p]) 21 if(!dfs(to[p])) return false; 22 return true; 23 } 24 25 void init(intn){ 26 this->n =n; 27 ecnt = 2; 28 memset(head,0,sizeof(head)); 29 memset(mark,0,sizeof(mark)); 30 } 31 32 void addEdge1(int x, int y){//x*y=false 33 to[ecnt] = y^1; next[ecnt] = head[x]; head[x] = ecnt++; 34 to[ecnt] = x^1; next[ecnt] = head[y]; head[y] = ecnt++; 35 } 36 37 void addEdge2(int x, int y){//x+y=true 38 to[ecnt] = y; next[ecnt] = head[x^1]; head[x^1] = ecnt++; 39 to[ecnt] = x; next[ecnt] = head[y^1]; head[y^1] = ecnt++; 40 } 41 42 boolsolve(){ 43 for(int i = 0; i < n*2; i += 2) 44 if(!mark[i] && !mark[i+1]){ 45 c = 0; 46 if(!dfs(i)) { 47 while(c>0) mark[St[--c]] = false; 48 if(!dfs(i^1)) return false; 49 } 50 } 51 return true; 52 } 53 } G; 54 55 intmain(){ 56 intn, m, a, b, c, d; 57 while(scanf("%d%d",&n,&m)!=EOF){ 58 G.init(n); 59 for(int i = 0; i < n; ++i) G.addEdge2(i*2,(i+n)*2); 60 while(m--){ 61 scanf("%d%d%d%d",&a,&b,&c,&d); 62 G.addEdge1((a + n*c)*2, (b + n*d)*2); 63 } 64 if(G.solve()) printf("YES "); 65 else printf("NO "); 66 } 67 return 0; 68 }
1 #include <cstdio> 2 #include <cstring> 3 using namespacestd; 4 5 const int MAXN = 2010; 6 const int MAXM = 1010*1010*2; 7 8 structTwoSAT{ 9 intn, ecnt, dfs_clock, scc_cnt; 10 int St[MAXN], c;//手动栈 11 inthead[MAXN], lowlink[MAXN], pre[MAXN], sccno[MAXN]; 12 intnext[MAXM], to[MAXM]; 13 14 void dfs(intu){ 15 pre[u] = lowlink[u] = ++dfs_clock; 16 St[++c] =u; 17 for(int p = head[u]; p; p =next[p]){ 18 int &v =to[p]; 19 if(!pre[v]){ 20 dfs(v); 21 if(lowlink[u] > lowlink[v]) lowlink[u] =lowlink[v]; 22 }else if(!sccno[v]){ 23 if(lowlink[u] > pre[v]) lowlink[u] =pre[v]; 24 } 25 } 26 if(lowlink[u] ==pre[u]){ 27 scc_cnt++; 28 while(true){ 29 int x = St[c--]; 30 sccno[x] =scc_cnt; 31 if(x == u) break; 32 } 33 } 34 } 35 36 void init(intn){ 37 this->n =n; 38 ecnt = 2; dfs_clock = scc_cnt = 0; 39 memset(head,0,sizeof(head)); 40 memset(sccno,0,sizeof(sccno)); 41 memset(pre,0,sizeof(pre)); 42 } 43 44 void addEdge1(int x, int y){//x*y=false 45 to[ecnt] = y^1; next[ecnt] = head[x]; head[x] = ecnt++; 46 to[ecnt] = x^1; next[ecnt] = head[y]; head[y] = ecnt++; 47 } 48 49 boolsolve(){ 50 for(int i = 0; i < n; ++i) 51 if(!pre[i]) dfs(i); 52 for(int i = 0; i < n; i += 2) 53 if(sccno[i] == sccno[i^1]) return false; 54 return true; 55 } 56 } G; 57 58 intmain(){ 59 intn, m, a, b, c, d; 60 while(scanf("%d%d",&n,&m)!=EOF){ 61 G.init(2*n); 62 while(m--){ 63 scanf("%d%d%d%d",&a,&b,&c,&d); 64 G.addEdge1(a*2 + c, b*2 +d); 65 } 66 if(G.solve()) printf("YES "); 67 else printf("NO "); 68 } 69 return 0; 70 }