HDU1824(2-SAT)

Let's go home

Time Limit: 10000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2103 Accepted Submission(s): 903

Problem Description

小时候，乡愁是一枚小小的邮票，我在这头，母亲在那头。
—— 余光中

集训是辛苦的，道路是坎坷的，休息还是必须的。经过一段时间的训练，lcy决定让大家回家放松一下，但是训练还是得照常进行，lcy想出了如下回家规定，每一个队（三人一队）或者队长留下或者其余两名队员同时留下；每一对队员，如果队员A留下，则队员B必须回家休息下，或者B留下，A回家。由于今年集训队人数突破往年同期最高记录，管理难度相当大，lcy也不知道自己的决定是否可行，所以这个难题就交给你了，呵呵，好处嘛~，免费**漂流一日。

Input

第一行有两个整数，T和M，1<=T<=1000表示队伍数，1<=M<=5000表示对数。
接下来有T行，每行三个整数，表示一个队的队员编号，第一个队员就是该队队长。
然后有M行，每行两个整数，表示一对队员的编号。
每个队员只属于一个队。队员编号从0开始。

Output

可行输出yes，否则输出no，以EOF为结束。

Sample Input

1 2 0 1 2 0 1 1 2 2 4 0 1 2 3 4 5 0 3 0 4 1 3 1 4

Sample Output

yes no

Author

威士忌

Source

HDOJ 2007 Summer Exercise（3）- Hold by Wiskey

2-SAT 建图

  1 //2017-08-27
  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("inputB.txt", "r", stdin);
 94     int t, m;
 95     while(cin>>t>>m){
 96         init();
 97         int MAXID = 3*t;
 98         int a, b, c;
 99         for(int i = 0; i < t; i++){
100             cin>>a>>b>>c;
101             add_edge(a+MAXID, b);// NOT a -> b
102             add_edge(a+MAXID, c);// NOT a -> c
103             add_edge(b+MAXID, a);// NOT b -> a
104             add_edge(c+MAXID, a);// NOT c -> a
105             //add_edge(b, c);
106             //add_edge(c, b);
107         }
108         for(int i = 0; i < m; i++){
109             cin>>a>>b;
110             add_edge(a, b+MAXID);
111             add_edge(b, a+MAXID);
112         }
113         scc(MAXID<<1);
114         solve(MAXID);
115     }
116     return 0;
117 }