HDU3062（2-SAT）

Party

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 6682 Accepted Submission(s): 2194

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 1 0 1 1 1

Sample Output

YES

Source

2009 Multi-University Training Contest 16 - Host by NIT

令夫为a，妻为a非

有矛盾的夫妻之间连边，不能出现在同一个强连通分量中。

  1 //2017-08-26
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <iostream>
  5 #include <algorithm>
  6 #include <vector>
  7 
  8 using namespace std;
  9 
 10 const int N = 5010;
 11 const int M = N*N;
 12 int head[N], rhead[N], tot, rtot;
 13 struct Edge{
 14     int to, next;
 15 }edge[M], redge[M];
 16 
 17 void init(){
 18     tot = 0;
 19     rtot = 0;
 20     memset(head, -1, sizeof(head));
 21     memset(rhead, -1, sizeof(rhead));
 22 }
 23 
 24 void add_edge(int u, int v){
 25     edge[tot].to = v;
 26     edge[tot].next = head[u];
 27     head[u] = tot++;
 28 
 29     redge[rtot].to = u;
 30     redge[rtot].next = rhead[v];
 31     rhead[v] = rtot++;
 32 }
 33 
 34 vector<int> vs;//后序遍历顺序的顶点列表
 35 bool vis[N];
 36 int cmp[N];//所属强连通分量的拓扑序
 37 
 38 //input: u 顶点
 39 //output: vs 后序遍历顺序的顶点列表
 40 void dfs(int u){
 41     vis[u] = true;
 42     for(int i = head[u]; i != -1; i = edge[i].next){
 43         int v = edge[i].to;
 44         if(!vis[v])
 45           dfs(v);
 46     }
 47     vs.push_back(u);
 48 }
 49 
 50 //input: u 顶点编号; k 拓扑序号
 51 //output: cmp[] 强连通分量拓扑序
 52 void rdfs(int u, int k){
 53     vis[u] = true;
 54     cmp[u] = k;
 55     for(int i = rhead[u]; i != -1; i = redge[i].next){
 56         int v = redge[i].to;
 57         if(!vis[v])
 58           rdfs(v, k);
 59     }
 60 }
 61 
 62 //Strongly Connected Component 强连通分量
 63 //input: n 顶点个数
 64 //output: k 强连通分量数;
 65 int scc(int n){
 66     memset(vis, 0, sizeof(vis));
 67     vs.clear();
 68     for(int u = 0; u < n; u++)
 69       if(!vis[u])
 70         dfs(u);
 71     int k = 0;
 72     memset(vis, 0, sizeof(vis));
 73     for(int i = vs.size()-1; i >= 0; i--)
 74       if(!vis[vs[i]])
 75         rdfs(vs[i], k++);
 76     return k;
 77 }
 78 
 79 void solve(int n){
 80     for(int i = 0; i < n; i++){
 81         if(cmp[i] == cmp[i+n]){//a和NOT a在同一个强连通分量中，布尔方程无解
 82             cout<<"NO"<<endl;
 83             return;
 84         }
 85     }
 86     cout<<"YES"<<endl;//布尔方程有解
 87     return;
 88 }
 89 
 90 int main()
 91 {
 92     std::ios::sync_with_stdio(false);
 93     //freopen("inputA.txt", "r", stdin);
 94     int n, m;
 95     while(cin>>n>>m){
 96         init();
 97         int u, v, a, b;
 98         for(int i = 0; i < m; i++){
 99             cin>>u>>v>>a>>b;
100             if(a == 0 && b == 0){// u && v
101                 add_edge(u+n, v);// NOT u -> v
102                 add_edge(v+n, u);// NOT v -> u
103             }else if(a == 0 && b == 1){// u && NOT v
104                 add_edge(u+n, v+n);// NOT u -> NOT v
105                 add_edge(v, u);// v -> u
106             }else if(a == 1 && b == 0){// NOT u && v
107                 add_edge(u, v);// u -> v
108                 add_edge(v+n, u+n);// NOT v -> NOT u
109             }else if(a == 1 && b == 1){// NOT u && NOT v
110                 add_edge(u, v+n);// u -> NOT v
111                 add_edge(v, u+n);// v -> NOT u
112             }
113         }
114         scc(n<<1);
115         solve(n);
116     }
117 
118     return 0;
119 }