hdu 1824 2-sat问题（判断）

/*

题意：u,v,w队长，队员，队长留下两个队员可以回家，两个队员留下，队长回家

2-sat问题，把两个队员看成一个整体就变成一个简单2-sat问题了

*/

#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<stdlib.h>

using namespace std;

#define N  6100

#define NN 5100

struct node {

int u,v,w,next;

}bian[NN*8];

int head[N],yong,low[N],dfn[N],belong[N],ans,top,index,stac[N],vis[N];

void init()

{

    memset(head,-1,sizeof(head));

    yong=index=ans=top=0;

    memset(vis,0,sizeof(vis));

    memset(dfn,0,sizeof(dfn));

}

void addedge(int u,int v)

{

    bian[yong].v=v;

    bian[yong].next=head[u];

    head[u]=yong++;

}

void tarjan(int u)

{

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

    stac[++top]=u;

    vis[u]=1;

    int i;

    for(i=head[u]; i!=-1; i=bian[i].next)

    {

        int v=bian[i].v;

        if(!dfn[v])

        {

            tarjan(v);

            low[u]=min(low[u],low[v]);

        }

        else if(vis[v])

            low[u]=min(low[u],dfn[v]);

    }

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

    {

        ans++;

        int t;

        do

        {

            t=stac[top--];

            belong[t]=ans;

            vis[t]=0;

        }

        while(t!=u);

    }

}

int slove(int n)

{

    int i;

    for(i=0; i<=n; i++)

        if(!dfn[i])

            tarjan(i);

    // printf("%d\n",ans);

    for(i=0; i<=n; i+=2)

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

            return 0;

    return 1;

}

int indx[N];

int main() {

    int n,m,i,u,len,v,w;

    while(scanf("%d%d",&n,&m)!=EOF) {

        init();

        len=-1;

        for(i=0;i<n;i++)  {

            scanf("%d%d%d",&u,&v,&w);

           indx[u]=++len;

           indx[v]=++len;

           indx[w]=len;

        }

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

            scanf("%d%d",&u,&v);

            addedge(indx[u],indx[v]^1);

            addedge(indx[v],indx[u]^1);

        }

        if(!slove(len))

            printf("no\n");

        else

            printf("yes\n");

    }

return 0;}
巴特西

hdu 1824 2-sat问题（判断）

最新文章

热门文章
