HDU3062 2-sat

  1 /*HDU3062
  2 2-sat入门
  3 虽然是入门，关于2-sat算法的实质的理解还是花了蛮久的时间。
  4 这道题还是有一些思维上的技巧。因为每对夫妇，最多且必须要去一个人，就是总共去了n个人。
  5 我开始时以每个人分别去否建模，这样还要满足上面的条件，显然算法是难以实现的。
  6 后来发现，只要以一对夫妻为对象，2i是丈夫去，2i+1是妻子去，非2i即2i+1，就像一件事情，非true即false
  7 所以，不仅是一个对象有true，false两种状态，推广开来，只要是二选一（排他率）的二值问题，就可以向2-sat方向思考。
  8 连边：因为2i和2i+1的相反关系，程序中已经能判断，所以不需考虑边的关系。
  9 仇人关系，先转化成对应的点a,b。（非a且b）或（a和非b），即是a^1和b连边，a和b^1连边
 10 判断是否是这个2-sat有解就可以了
 11 */
 12 #include <stdio.h>
 13 #include <stdlib.h>
 14 #include <string.h>
 15 #include <math.h>
 16 #include <ctype.h>
 17 #include <string>
 18 #include <iostream>
 19 #include <sstream>
 20 #include <vector>
 21 #include <queue>
 22 #include <stack>
 23 #include <map>
 24 #include <list>
 25 #include <set>
 26 #include <algorithm>
 27 #define INF 0x3f3f3f3f
 28 #define LL long long
 29 #define eps 1e-7
 30 #define maxn 1100
 31 using namespace std;
 32 struct TwoSAT{
 33     int n;
 34     vector<int> G[maxn*2];//注意点集的大小
 35     bool mark[maxn*2];//联系《2-sat算法解析》中的红蓝标色，夫妻不能被标同一种颜色；因为仇人间没有连边，所以在图本身，不可能将两人标同一个颜色
 36     int S[maxn*2],c;//存储当前被标记的点，可用于标记的回退
 37 
 38     bool dfs(int x)
 39     {
 40         if (mark[x^1]) return false;//真假同时被标记，逻辑矛盾
 41         if (mark[x]) return true;//x被标记，意味着下面的节点也被标记，思想是记忆化搜索
 42         mark[x]=true;
 43         S[c++]=x;
 44         for(int i=0;i<G[x].size();i++)
 45             if(!dfs(G[x][i])) return false;//同一个强联通分量应该表上同一种颜色
 46         return true;
 47     }
 48 
 49     void init(int n)
 50     {
 51         this->n=n;
 52         for(int i=0;i<n*2;i++) G[i].clear();
 53         memset(mark,0,sizeof(mark));
 54     }
 55 
 56     void add_edge(int u,int v)//这个地方灵活多变一点
 57     {
 58         G[u].push_back(v);
 59 //        cout<<u<<"->"<<v<<endl;
 60     }
 61 
 62     bool solve()
 63     {
 64         for(int i=0;i<n*2;i+=2)
 65         {
 66             if(!mark[i] && !mark[i^1])//真假都没被标记才需dfs，思考一下，原书上写的是[mark+1],这是由i的取值和步长决定的，这里更改，使逻辑含义统一
 67             {
 68                 c=0;//记得清零
 69                 if(!dfs(i))//将i标记为true
 70                 {
 71                     while(c>0) mark[S[--c]]=false;
 72                     if (!dfs(i^1)) return false;//更改初始标号颜色。只要有一个对象不能“二选一”，则2-sat无解
 73                 }
 74             }
 75         }
 76         return true;
 77     }
 78 }sat;
 79 //2i是丈夫去，2i+1是妻子去，
 80 //仇人关系，先转化成对应的点a,b。（非a且b）或（a和非b），即是a^1和b连边，a和b^1连边,注意是双向边，满足对偶性
 81 int n,m;
 82 int nextint()
 83 {
 84     int x;
 85     scanf("%d",&x);
 86     return x;
 87 }
 88 int main()
 89 {
 90     while(cin>>n>>m)
 91     {
 92 //        cout<<"Sdf"<<endl;
 93         sat.init(n);//记住标号为相应的0--n-1
 94         for(int i=1;i<=m;i++)
 95         {
 96             int a1,a2,c1,c2;
 97             int a,b;
 98             a1=nextint();
 99             a2=nextint();
100             c1=nextint();
101             c2=nextint();
102             if(c1==0) a=a1*2+1;else a=a1*2;//0是妻子
103             if(c2==0) b=a2*2+1;else b=a2*2;
104 //            sat.add_edge(a^1,b);
105             sat.add_edge(b,a^1);
106             sat.add_edge(a,b^1);
107 //            sat.add_edge(b^1,a);
108         }
109         if (sat.solve()) cout<<"YES"<<endl;else cout<<"NO"<<endl;
110     }
111 }