Hdu 1824 【2sat】.cpp

题意：

　　　n个队伍，一个队伍3个人，要求如果队长不在那剩下两个队员必须在，如果剩下两个队员不在队长必须在..

　　　m种冲突关系，每种冲突关系中的两个人不能同时存在。

　　问方案是否可行..

思路：

　　2-sat..根据冲突关系连边..

　　然后看某人的留和不留是否会一起发生..如果会就代表方案不可行..

Tips：

　　总结一下2-sat..

　　通常都需要拆点..拆成两种状态，选或者不选..

　　然后根据题目给出的点的必然关系..即a发生b不能发生，b发生a不能发生..的关系连边..

　　根据建的图进行深搜..并且染色..

　　最后结果就是必须发生的关系的总关系会是一种颜色..

　　最后遍历每一个点，如果该点的选或者不选是同一种颜色..就代表如果该点选，那么经过题目给出的点之间的必然关系..该点同时需要不被选中..

　　所以该点的状态就是冲突的..方案就是不可行的..

Code：

View Code

 1 #include <stdio.h>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 #define clr(x) memset(x, 0, sizeof(x))
 6 
 7 const int INF = 0x1f1f1f1f;
 8 const int MAXM = 1000010;
 9 const int MAXN = 6010;
10 
11 struct Edge
12 {
13     int to;
14     int next;
15 }edge[MAXM];
16 int tot;
17 int head[MAXN];
18 
19 void add(int s, int u)
20 {
21     edge[tot].to = u;
22     edge[tot].next = head[s];
23     head[s] = tot++;
24 }
25 
26 int low[MAXN], dfn[MAXN];
27 int sta[MAXN], ins[MAXN], col[MAXN];
28 int ti, top, cnt;
29 
30 void tarjan(int u)
31 {
32     dfn[u] = low[u] = ++ti;
33     ins[u] = 1;
34     sta[++top] = u;
35     for (int i = head[u]; i != -1; i = edge[i].next) {
36         int k = edge[i].to;
37         if (dfn[k] == 0) {
38            tarjan(k);
39            low[u] = min(low[u], low[k]);
40         } else if (ins[k] != 0) {
41             low[u] = min(low[u], dfn[k]);
42         }
43     }
44     if (low[u] == dfn[u]) {
45         cnt++;
46         int k;
47         do {
48             k = sta[top--];
49             col[k] = cnt;
50             ins[k] = 0;
51         } while (u != k);
52     }
53 }
54 
55 int n, m;
56 
57 void solva_ta()
58 {
59     clr(dfn);
60     clr(ins);
61     ti = top = cnt = 0;
62     for (int i = 0; i < 6*n; ++i)
63         if (dfn[i] == 0)
64             tarjan(i);
65 }
66 
67 int main()
68 {
69    // freopen("in.txt", "r", stdin);
70     int a, b, c;
71     bool flag;
72     while (~scanf("%d %d", &n, &m)) {
73         tot = 0;
74         memset(head, 0xff, sizeof(head));
75         flag = true;
76         for (int i = 0; i < n; ++i) {
77             scanf("%d %d %d", &a, &b, &c);
78             add(a+3*n, b), add(a+3*n, c); //add(b, c);
79             add(b+3*n, a), add(c+3*n, a);
80         }
81         for (int i = 0; i < m; ++i) {
82             scanf("%d %d", &a, &b);
83             add(b, a+3*n), add(a, b+3*n);
84         }
85         solva_ta();
86         for (int i = 0; i < 3*n; ++i)
87             if (col[i] == col[i+3*n]) {
88                 flag = false;
89                 break;
90             }
91         if (flag) puts("yes");
92         else puts("no");
93     }
94     return 0;
95 }

链接：http://acm.hdu.edu.cn/showproblem.php?pid=1824