http://codeforces.com/gym/100502/attachments
题意：有n个地点，m条边，每条边有一个边权，0代表两个顶点都染成白色，2代表两个顶点都染成黑色，1代表两个顶点可能尚未染色，但是之后必须一个染成白色一个染成黑色。问是否有可能让这个图成功染色，如果可能输出染成黑色的最少顶点数。
思路：一开始0和2的边是确定的，直接染，如果有矛盾直接false。然后利用边权为1的边建图。先考虑如果图中的某个点已经染色了，那么直接DFS染色，然后这个阶段出现黑色的点是确定的（因为必须染成这个颜色），如果出现矛盾就返回。
再考虑如果图中没有点染色，这个时候随便染一种颜色，用两个计数器a和b，代表这个阶段染成白色的点和黑色的点的数目，这个对答案的贡献为min(a, b)，因为点都是不确定的，所以染成白和染成黑都是一样的，所以可以互换，然后出现矛盾就返回。
#include <bits/stdc++.h>
using namespace std;
#define N 200010
struct Edge {
int v, nxt;
} edge[N*];
int vis[N], head[N], tot, col[N], a, b, ans; void Add(int u, int v) {
edge[tot] = (Edge) {v, head[u]}; head[u] = tot++;
edge[tot] = (Edge) {u, head[v]}; head[v] = tot++;
} bool DFS(int u, int c, int kind) {
if(kind) {
if(col[u] == ) b++; else a++;
} else {
if(col[u] == ) ans++;
}
for(int i = head[u]; ~i; i = edge[i].nxt) {
int v = edge[i].v;
if(col[v] == c) return false;
if(!vis[v]) { vis[v] = ; if(col[v] == ) col[v] = -c; if(!DFS(v, col[v], kind)) return false; }
}
return true;
} int main() {
int n, m;
scanf("%d%d", &n, &m);
memset(head, -, sizeof(head));
bool flag = ;
for(int i = ; i < m; i++) {
int u, v, k;
scanf("%d%d%d", &u, &v, &k);
if(k == ) {
if(col[u] == - || col[v] == -) flag = ;
col[u] = col[v] = ;
} else if(k == ) {
if(col[u] == || col[v] == ) flag = ;
col[u] = col[v] = -;
} else Add(u, v);
}
for(int i = ; i <= n; i++)
if(!vis[i] && col[i]) { vis[i] = ; if(!DFS(i, col[i], )) flag = ; }
for(int i = ; i <= n; i++) {
if(vis[i]) continue;
a = ; b = ; vis[i] = ; col[i] = ;
if(!DFS(i, , )) flag = ;
ans += a > b ? b : a;
}
if(!flag) puts("impossible");
else printf("%d\n", ans);
return ;
}