ZJU 3422 && HDU 3715 Go Deeper

时间：2010-11-24 来源：晓天

看到a、b只能选择0，1就应该想到是2-sat问题。

建图方法：

2-sat箴言：如果a与b矛盾，则添加单向边(a,b').

这道题目中，矛盾指的是a[i]+b[i]=c[i].故可应该按如下方法建图。

假设，a代表0，a'代表1.

1、c=0时，a=0时，b=0时产生矛盾，故连边(a,b'),(b,a')；

a=1时不会有矛盾。

2、c=1时，a=0时，b=1时产生矛盾，故连边(a,b),(b',a')；

a=1时，b=0时产生矛盾，故连边(a',b'),(b,a)；

3、c=2时，a=0时，不会产生矛盾。

a=1时，b=1时产生矛盾，故连边(a,b),(b,a)。

建图完毕，直接上2-sat模板（其实就是强连通分量的模板）就可以，当然这里还要二分。

代码

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<vector>
using namespace std;
#define N 408
#define M 10008
#define inf 0x7ffffff
vector<int>g[N];
int id[N], pre[N], low[N], s[N], stop, cnt, scnt;

void tarjan(int v, int n) {
    //printf("%d\n",n);
    int t, minc = low[v] = pre[v] = cnt++;
    s[stop++] = v;
    for (int i = 0; i < g[v].size(); i++) {
        if (-1 == pre[g[v][i]]) tarjan(g[v][i], n);
        if (low[g[v][i]] < minc) minc = low[g[v][i]];
    }
    if (minc < low[v]) {
        low[v] = minc;
        return;
    }
    do {
        id[t = s[--stop]] = scnt;
        low[t] = n;
    } while (t != v);
    ++scnt;
}
int n, m;
int A[M], B[M], C[M];

bool _2sat() {
    stop = cnt = scnt = 0;
    memset(pre, -1, sizeof (pre));
    int nn = n * 2;
    for (int i = 0; i < nn; ++i) if (-1 == pre[i]) tarjan(i, nn);
    for (int i = 0; i < n; i++) if (id[i] == id[i + n]) return 0;
    return 1;
}

void add(int a, int b) {
    g[a].push_back(b);
}

void build(int mid) {
    for (int i = 0; i < N; i++) g[i].clear();
    int a, b, c;
    for (int i = 0; i < mid; i++) {
        a = A[i], b = B[i], c = C[i];
        switch (c) {
            case 0: add(a, b + n), add(b, a + n);
                break;
            case 1: add(a, b), add(b, a), add(a + n, b + n), add(b + n, a + n);
                break;
            case 2: add(b + n, a), add(a + n, b);
                break;
        }
    }
}

int main() {
    freopen("in", "r", stdin);
    int tc;
    scanf("%d", &tc);
    while (tc--) {
        scanf("%d%d", &n, &m);
        for (int i = 0; i < m; i++)
            scanf("%d%d%d", A + i, B + i, C + i);
        int l = 0, r = m, mid;
        while (l <= r) {
            mid = (l + r) >> 1;
            build(mid);
            if (_2sat()) l = mid + 1;
            else r = mid - 1;
        }
        printf("%d\n", l - 1);
    }
    return 0;
}