学步园

HDU_3715

     我的第二个2-SAT的题目，^_^。整体的思路是二分深度，然后观察当前深度下是否能够推出矛盾。

对于任意一个x[]只有0或1两种取值，并且只能为其中一种，为了便于分析，我们不妨设a[dep]的值为i，设b[dep]的值为j，设c[dep]的值为k，2*i这个点代表x[i]取0，2*i+1这个点代表x[i]取1。

k一共有0、1、2三种取值，我们不妨分情况讨论一下x[]需要满足什么条件才可以达到下一个depth：

①当k=2时，如果x[i]为1，那么x[j]必然为0，于是需要连一条有向边2*i+1->j，同理，如果x[j]为1，那么x[i]必然为0，于是需要连另一条有向边2*j+1->i。

②当k=1时，如果x[i]为0，则x[j]必然为0，如果x[i]为1，则x[j]必然为1，同理如果x[j]为0，则x[i]必然为0，如果x[j]为1，则x[i]必然为1，连上对应的4条边即可。

③当k=0时，如果x[i]为0，则x[j]必然为1，同理，如果x[j]为0，则x[i]必然为1，连上对应的2条边即可。

     剩下的工作只要运用tarjan算法求强连通分量、缩点，然后判断是否有有一对数2*i、2*i+1在一个强连通分量内（即能否推出矛盾——x[i]是必须为0同时又必须为1）即可。

#include<stdio.h>
#include<string.h>
#define MAXD 410
#define MAXM 40010
int a[MAXM], b[MAXM], c[MAXM], n, m;
int first[MAXD], next[MAXM], v[MAXM];
int dfn[MAXD], low[MAXD], cnt;
int top, s[MAXD], ins[MAXD], color[MAXD], col;
void init()
{
int i;
    scanf("%d%d", &n, &m);
for(i = 0; i < m; i ++)
        scanf("%d%d%d", &a[i], &b[i], &c[i]);
}
void tarjan(int u)
{
int i, e;
    dfn[u] = low[u] = ++ cnt;
for(e = first[u]; e != -1; e = next[e])
    {
if(!dfn[v[e]])
        {
            s[top ++] = v[e];
            ins[v[e]] = 1;
            tarjan(v[e]);
if(low[v[e]] < low[u])
                low[u] = low[v[e]];
        }
else if(ins[v[e]] && dfn[v[e]] < low[u])
            low[u] = dfn[v[e]];
    }
if(low[u] == dfn[u])
    {
for(s[top] = -1; s[top] != u;)
        {
            top --;
            ins[s[top]] = 0;
            color[s[top]] = col;
        }
        col ++;
    }
}
int com(int mid)
{
int i, e, x1, x2;
    memset(first, -1, sizeof(first));
    e = 0;
for(i = 0; i < mid; i ++)
    {
if(c[i] == 2)
        {
            x1 = 2 * a[i] + 1;
            x2 = 2 * b[i];
            v[e] = x2;
            next[e] = first[x1];
            first[x1] = e;
            e ++;

            x1 = 2 * a[i];
            x2 = 2 * b[i] + 1;
            v[e] = x1;
            next[e] = first[x2];
            first[x2] = e;
            e ++;
        }
else if(c[i] == 1)
        {
            x1 = 2 * a[i];
            x2 = 2 * b[i];
            v[e] = x2;
            next[e] = first[x1];
            first[x1] = e;
            e ++;
            v[e] = x1;
            next[e] = first[x2];
            first[x2] = e;
            e ++;

            x1 = 2 * a[i] + 1;
            x2 = 2 * b[i] + 1;
            v[e] = x2;
            next[e] = first[x1];
            first[x1] = e;
            e ++;
            v[e] = x1;
            next[e] = first[x2];
            first[x2] = e;
            e ++;
        }
else
        {
            x1 = 2 * a[i];
            x2 = 2 * b[i] + 1;
            v[e] = x2;
            next[e] = first[x1];
            first[x1] = e;
            e ++;

            x1 = 2 * a[i] + 1;
            x2 = 2 * b[i];
            v[e] = x1;
            next[e] = first[x2];
            first[x2] = e;
            e ++;
        }
    }
    cnt = top = col =0;
    memset(ins, 0, sizeof(ins));
    memset(dfn, 0, sizeof(dfn));
for(i = 0; i < 2 * n; i ++)
if(!dfn[i])
        {
            s[top ++] = i;
            ins[i] = 1;
            tarjan(i);
        }
for(i = 0; i < 2 * n; i ++)
if(color[i] == color[i ^ 1])
return 0;
return 1;
}
int main()
{
int i, j, k, t, min, max, mid;
    scanf("%d", &t);
while(t --)
    {
        init();
        max = m + 1;
        min = 0;
for(;;)
        {
            mid = (max + min) / 2;
if(mid == min)
break;
if(com(mid))
                min = mid;
else
                max = mid;
        }
        printf("%d\n", mid);

    }
return 0;    
}