CSU 1574 Amanda Lounges (二分图）

题目链接：http://acm.csu.edu.cn/csuoj/problemset/problem?pid=1574

先把0和2能确定的给确定下来，同时判断矛盾，把1的单独拿出来建图

对新建的图进行第一次dfs，因为还有一些点可以确定，同时判断矛盾

第二次dfs，此时所有能确定的点都已经确定了，只剩下不确定的点了，对所有不确定的点进行dfs，先假设他为1，然后类似于判断二分图那样的dfs找出最小的答案，同时判断矛盾

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
int used[MAXN];
vector<int> G[MAXN];
typedef pair<int,int> pp;
int flag;
void dfs1(int u,int father,int val)
{
    for(int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if(v == father || used[v] == -val) continue;
        if(used[v] == val) {
            flag = 1;
            return;
        }
        used[v] = -val;
        dfs1(v,u,-val);
    }
}
pp dfs2(int u,int father,int val)
{
    pp res = make_pair(0,0);
    if(val == 1) res.first++;
    else res.second++;
    for(int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if(v == father || used[v] == -val) continue;
        if(used[v] == val) {
            flag = 1;
            return res;
        }
        used[v] = -val;
        pp temp = dfs2(v,u,-val);
        res.first += temp.first;
        res.second += temp.second;
    }
    return res;
}
int main(void)
{
    int n,m,ans,u,v,val;
    while(scanf("%d %d",&n,&m) != EOF) {
        flag = ans = 0;
        memset(used,0,sizeof(used));
        for(int i = 1; i <= n; i++) {
            G[i].clear();
        }
        while(m--) {
            scanf("%d %d %d",&u,&v,&val);
            val--;
            if(val) {
                if(used[u] == 0) used[u] = val;
                else if(used[u] == -val) {flag = 1,used[u] = val;}
                if(used[v] == 0) used[v] = val;
                else if(used[v] == -val) {flag = 1,used[v] = val;}
            }
            else {
                G[u].push_back(v);
                G[v].push_back(u);
            }
        }
        if(flag) {
            printf("impossible\n");
            continue;
        }
        for(int i = 1; i <= n; i++) {
            if(used[i]) dfs1(i,i,used[i]);
            if(flag) break;
        }
        if(flag) {
            printf("impossible\n");
            continue;
        }
        for(int i = 1; i <= n; i++) {
            if(used[i] == 1) ans++;
        }
        pp res;
        for(int i = 1; i <= n; i++) {
            if(used[i] == 0) {
                used[i] = 1;
                res = dfs2(i,i,1);
                if(flag) break;
                else ans += min(res.first,res.second);
            }
        }
        if(flag) printf("impossible\n");
        else printf("%d\n",ans);
    }
    return 0;
}