[2-sat]HDOJ1824Let'sgohome

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› Go›Go教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

中问题题意略

和HDOJ 3062 一样

这里每个队员都有选和不选两种，即上篇所说的$x$和$x’$

建图：队长(a)留下或者其余两名队员(b、c)同时留下

那么就是$a' \Rightarrow b$ 、 $a' \Rightarrow c$ (队长不在 b必须在，队长不在 c必须在)

　　　　以及$b' \Rightarrow a$ 、$c' \Rightarrow a$ (b不在队长必须在，c不在队长必须在)

　　每一对队员，如果队员A留下，则队员B必须回家休息下，或者B留下，A回家

　　那么就是$A \Rightarrow B’$ (A在则B必须不在) 以及 $B \Rightarrow A'$ (B在则A必须不在)

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 typedef pair<int, int> PI;
 5 #define INF 0x3f3f3f3f
 6 
 7 const int N=3005*2;
 8 const int M=N*N;
 9 //注意n是拆点后的大小 即 n <<= 1 N为点数(注意要翻倍) M为边数 i&1=0为i真 i&1=1为i假
10 struct Edge
11 {
12     int to, nex;
13 }edge[M];
14 //注意 N M 要修改
15 int head[N], edgenum;
16 void addedge(int u, int v)
17 {
18     Edge E={v, head[u]};
19     edge[edgenum]=E;
20     head[u]=edgenum++;
21 }
22 
23 bool mark[N];
24 int Stack[N], top;
25 void init()
26 {
27     memset(head, -1, sizeof(head));
28     edgenum=0;
29     memset(mark, 0, sizeof(mark));
30 }
31 
32 bool dfs(int x)
33 {
34     if(mark[x^1])
35         return false;//一定是拆点的点先判断
36     if(mark[x])
37         return true;
38     mark[x]=true;
39     Stack[top++]=x;
40     for(int i=head[x];i!=-1;i=edge[i].nex)
41         if(!dfs(edge[i].to))
42             return false;
43 
44     return true;
45 }
46 
47 bool solve(int n)
48 {
49     for(int i=0;i<n;i+=2)
50         if(!mark[i] && !mark[i^1])
51         {
52             top=0;
53             if(!dfs(i))
54             {
55                 while(top)
56                     mark[Stack[--top]]=false;
57                 if(!dfs(i^1))
58                     return false;
59             }
60         }
61     return true;
62 }
63 
64 int main()
65 {
66     int n, m;
67     while(~scanf("%d%d", &n, &m))
68     {
69         int nn=n*3;
70         init();
71         while(n--)
72         {
73             int a, b, c;
74             scanf("%d%d%d", &a, &b, &c);
75             addedge(a*2+1, b*2);
76             addedge(a*2+1, c*2);
77             addedge(b*2+1, a*2);
78             addedge(c*2+1, a*2);
79         }
80         while(m--)
81         {
82             int x, y;
83             scanf("%d%d", &x, &y);
84             addedge(x*2, y*2+1);
85             addedge(y*2, x*2+1);
86         }
87         solve(nn)? puts("yes"): puts("no");
88     }
89     return 0;
90 }