Go Deeper

题意：确定一个0/1数组（size:n）使得满足最多的条件数。条件在数组a,b,c给出。

吐槽：哎，一水提，还搞了很久！关键是抽象出题目模型（如上的一句话）。以后做二sat：有哪些是点，哪些是条件，分清！，然后注意细节。这次居然因为里面一个小错误：

判断有无解的时候，i与i+1是否在一个SCC中的时候，i居然没有每次+2!而是++！傻X了。。。囧！还一直以为自己二分写错。。。

#include<iostream>

#include<cstdio>

#include<stack>

#include<vector>

using namespace std;

const int inf=0x3f3f3f3f;

const int maxv=402;//maxe=500000;

int dfn[maxv];int low[maxv];int vis[maxv];int scc[maxv];int ins[maxv];stack<int>sta;

int times=0; int numb=0;

vector<vector<int> >e(maxv);

void tarjan(int u)

{

     dfn[u]=low[u]=times++;

     ins[u]=1;

     sta.push(u);

     for(int i=0;i<e[u].size();i++)

     {

         int v=e[u][i];

         if(!vis[v])

         {

             vis[v]=1;

             tarjan(v);

             if(low[v]<low[u])low[u]=low[v];

         }

         else if(ins[v]&&dfn[v]<low[u])

            low[u]=dfn[v];

     }

     if(low[u]==dfn[u])

     {

         numb++;

         int cur;

         do{

             cur=sta.top();

             sta.pop();

             ins[cur]=0;

             scc[cur]=numb;

         }while(cur!=u);

     }

}

int n,m;int a[10005],b[10005],c[10005];

void init()

{

    numb=times=0;

    for(int i=0;i<maxv;i++)

      {

         scc[i]=ins[i]=dfn[i]=low[i]=vis[i]=0;

         e[i].clear();

      }

}

bool build_solve(int x)

{

    init();

    for(int i=0;i<=x;i++)

    {

        if(c[i]==2)

        {

            e[2*a[i]+1].push_back(2*b[i]);

            e[2*b[i]+1].push_back(2*a[i]);

        }

        else if(c[i]==1)

        {

            e[2*a[i]].push_back(2*b[i]);

            e[2*b[i]].push_back(2*a[i]);

            e[2*a[i]+1].push_back(2*b[i]+1);

            e[2*b[i]+1].push_back(2*a[i]+1);

        }

        else if(c[i]==0)

        {

            e[2*a[i]].push_back(2*b[i]+1);

            e[2*b[i]].push_back(2*a[i]+1);

        }

    }

    for(int i=0;i<=2*n-1;i++)

    {

        if(!vis[i])

        {

            vis[i]=1;

            tarjan(i);

        }

    }

   for(int i=0;i<=2*n-2;i+=2)            //开始写成i++！！！！WA到跪！

        if(scc[i]==scc[i+1])

            return 0;

  return 1;

}

void readin()

{

    for(int i=0;i<m;i++)

        scanf("%d%d%d",&a[i],&b[i],&c[i]);

}

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d%d",&n,&m);

        init();

        readin();

        int l=0,r=m,mid;

        while(l+1<r)

        {

            mid=(l+r)/2;

            if(build_solve(mid))

                l=mid;

            else

                r=mid;

        }

        printf("%d\n",l+1);

    }

    return 0;

}

巴特西

hdu3715 2-sat+二分

Go Deeper

最新文章

热门文章