http://poj.org/problem?id=3678
题意:
一些点，点的取值可以是0或者1，没有告诉你具体取值。
一些边，有权值，有运算方式（并，或，异或），要求和这条边相连的两个点经过边上的运算后的结果是边的权值。
问你有没有可能把每个点赋值满足所有边的要求。
解题报告：（找矛盾 。必须 关系）
a and b == 1, 这种情况a和b必须取1，所以连边a->a', b->b'.
a and b == 0, 这种情况a和b不能同时为1，所以连边a'->b, b'->a.
a or b == 1, 这种情况a和b不能同时为0，所以连边a->b', b->a'.
a or b == 0, 这种情况a和b必须同时为0，所以连边a'->a, b'->b.
a xor b == 1, 这种情况a和b取值要相反，所以连边a->b', a'->b, b->a', b'->a.
a xor b == 0, 这种情况a和b取值要相同，所以连边a->b, b->a, a'->b', b'->a'.
a and b == 0, 这种情况a和b不能同时为1，所以连边a'->b, b'->a.
a or b == 1, 这种情况a和b不能同时为0，所以连边a->b', b->a'.
a or b == 0, 这种情况a和b必须同时为0，所以连边a'->a, b'->b.
a xor b == 1, 这种情况a和b取值要相反，所以连边a->b', a'->b, b->a', b'->a.
a xor b == 0, 这种情况a和b取值要相同，所以连边a->b, b->a, a'->b', b'->a'.
不能为0的处理时：如果i取0，那么i就要取1.
原理 http://blog.sina.com.cn/s/blog_68629c7701010gf1.html
即：i -> i + n。
1 #include<cstdio>
2 #include<cstring>
3 #include<cmath>
4 #include<iostream>
5 #include<algorithm>
6 #include<set>
7 #include<map>
8 #include<queue>
9 #include<vector>
10 #include<string>
11 #define Min(a,b) a<b?a:b
12 #define Max(a,b) a>b?a:b
13 #define CL(a,num) memset(a,num,sizeof(a));
14 #define eps 1e-12
15 #define inf 100000000
16 #define mx 1<<60
17 #define ll __int64
18 const double pi = acos(-1.0);
19 const int maxn = 3000;
20 using namespace std;
21 int top,num,bcnt,belong[maxn],instack[maxn],stack[maxn],dfn[maxn],low[maxn];
22 int n ,m;
23
24 struct pnode
25 {
26 int to;
27 int next;
28 }p[3000000];
29
30 int cnt ,next[maxn];
31 void add(int u,int v)
32 {
33 p[cnt].to = v;
34 p[cnt].next = next[u];
35 next[u] = cnt++;
36
37 }
38 void tarjan(int i)
39 {
40 int j,k;
41 dfn[i] = low[i] = ++num;
42 stack[++top] = i;
43 instack[i] = 1;
44 for(k = next[i] ; k != -1;k = p[k].next)
45 {
46
47 j = p[k].to ;
48 if(!dfn[j])
49 {
50 tarjan(j);
51 if(low[j] < low[i]) low[i] = low[j] ;
52 }
53 else
54 {
55 if(instack[j] && dfn[j] < low[i]) low[i] = dfn[j] ;
56 }
57
58 }
59 if(dfn[i] == low[i])
60 {
61 bcnt++;
62 do
63 {
64 j = stack[top--];
65 instack[j] = 0 ;
66 belong[j] = bcnt ;
67 }while(j != i);
68 }
69 }
70 void solve()
71 {
72 int i, l;
73 for(i =0 ; i <= n*2;i++)
74 {
75 dfn[i] = low[i] = instack[i] = stack[i] = belong[i] = 0;
76 }
77 top = bcnt = num = 0;
78 for(i = 0 ; i < n*2;i++)
79 {
80 if(!dfn[i])tarjan(i);
81 }
82 bool f = true ;
83 for(i = 0 ; i < n;i++)
84 {
85
86 if(belong[i] == belong[i+n])
87 {
88
89 f = false ;
90 break ;
91 }
92 }
93
94 if(f) printf("YES\n");
95 else
96 printf("NO\n");
97 }
98 void init()
99 {
100 CL(next,-1);
101 cnt = 0 ;
102
103 }
104 int main()
105 {
106 int i,j,a,b,c;
107 char str[4] ;
108 //freopen("data.txt","r",stdin) ;
109
110 while(scanf("%d%d",&n,&m)!=EOF)
111 {
112 init() ;
113 for(i = 0 ;i< m;i++)
114 {
115 scanf("%d %d %d %s",&a,&b,&c,str);
116 if(str[0]=='A')
117 {
118 if(c == 0)
119 {
120 add(a + n,b );
121 add(b+n,a) ;
122
123 }
124 else
125 {
126 add(a + n,b + n);
127 add(b + n,a+n);
128 add(a,a+n);//注意这
129 add(b,b+n);
130
131
132
133 }
134
135 }
136 if(str[0] == 'O')
137 {
138 if(c == 0)
139 {
140 add(a ,b);
141 add(b,a);
142 add(a + n,a);//注意这
143 add(b+n,b) ;
144
145
146
147
148
149 }
150 else
151 {
152 add(a,b + n);
153
154 add(b,a+n);
155
156
157
158
159
160 }
161 }
162 if(str[0] == 'X')
163 {
164 if(c == 0)
165 {
166 add(a ,b);
167 add(b,a);
168 add(a + n,b+ n);
169 add(b + n,a+n);
170
171
172 }
173 else
174 {
175 add(a,b + n);
176 add(b + n,a);
177 add(a+n,b );
178 add(b,a+n);
179
180
181 }
182 }
183 }
184 solve() ;
185 }
186 }
2 #include<cstring>
3 #include<cmath>
4 #include<iostream>
5 #include<algorithm>
6 #include<set>
7 #include<map>
8 #include<queue>
9 #include<vector>
10 #include<string>
11 #define Min(a,b) a<b?a:b
12 #define Max(a,b) a>b?a:b
13 #define CL(a,num) memset(a,num,sizeof(a));
14 #define eps 1e-12
15 #define inf 100000000
16 #define mx 1<<60
17 #define ll __int64
18 const double pi = acos(-1.0);
19 const int maxn = 3000;
20 using namespace std;
21 int top,num,bcnt,belong[maxn],instack[maxn],stack[maxn],dfn[maxn],low[maxn];
22 int n ,m;
23
24 struct pnode
25 {
26 int to;
27 int next;
28 }p[3000000];
29
30 int cnt ,next[maxn];
31 void add(int u,int v)
32 {
33 p[cnt].to = v;
34 p[cnt].next = next[u];
35 next[u] = cnt++;
36
37 }
38 void tarjan(int i)
39 {
40 int j,k;
41 dfn[i] = low[i] = ++num;
42 stack[++top] = i;
43 instack[i] = 1;
44 for(k = next[i] ; k != -1;k = p[k].next)
45 {
46
47 j = p[k].to ;
48 if(!dfn[j])
49 {
50 tarjan(j);
51 if(low[j] < low[i]) low[i] = low[j] ;
52 }
53 else
54 {
55 if(instack[j] && dfn[j] < low[i]) low[i] = dfn[j] ;
56 }
57
58 }
59 if(dfn[i] == low[i])
60 {
61 bcnt++;
62 do
63 {
64 j = stack[top--];
65 instack[j] = 0 ;
66 belong[j] = bcnt ;
67 }while(j != i);
68 }
69 }
70 void solve()
71 {
72 int i, l;
73 for(i =0 ; i <= n*2;i++)
74 {
75 dfn[i] = low[i] = instack[i] = stack[i] = belong[i] = 0;
76 }
77 top = bcnt = num = 0;
78 for(i = 0 ; i < n*2;i++)
79 {
80 if(!dfn[i])tarjan(i);
81 }
82 bool f = true ;
83 for(i = 0 ; i < n;i++)
84 {
85
86 if(belong[i] == belong[i+n])
87 {
88
89 f = false ;
90 break ;
91 }
92 }
93
94 if(f) printf("YES\n");
95 else
96 printf("NO\n");
97 }
98 void init()
99 {
100 CL(next,-1);
101 cnt = 0 ;
102
103 }
104 int main()
105 {
106 int i,j,a,b,c;
107 char str[4] ;
108 //freopen("data.txt","r",stdin) ;
109
110 while(scanf("%d%d",&n,&m)!=EOF)
111 {
112 init() ;
113 for(i = 0 ;i< m;i++)
114 {
115 scanf("%d %d %d %s",&a,&b,&c,str);
116 if(str[0]=='A')
117 {
118 if(c == 0)
119 {
120 add(a + n,b );
121 add(b+n,a) ;
122
123 }
124 else
125 {
126 add(a + n,b + n);
127 add(b + n,a+n);
128 add(a,a+n);//注意这
129 add(b,b+n);
130
131
132
133 }
134
135 }
136 if(str[0] == 'O')
137 {
138 if(c == 0)
139 {
140 add(a ,b);
141 add(b,a);
142 add(a + n,a);//注意这
143 add(b+n,b) ;
144
145
146
147
148
149 }
150 else
151 {
152 add(a,b + n);
153
154 add(b,a+n);
155
156
157
158
159
160 }
161 }
162 if(str[0] == 'X')
163 {
164 if(c == 0)
165 {
166 add(a ,b);
167 add(b,a);
168 add(a + n,b+ n);
169 add(b + n,a+n);
170
171
172 }
173 else
174 {
175 add(a,b + n);
176 add(b + n,a);
177 add(a+n,b );
178 add(b,a+n);
179
180
181 }
182 }
183 }
184 solve() ;
185 }
186 }