程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 3062 Party (2-sat)

HDU 3062 Party (2-sat)

編輯：C++入門知識

HDU 3062 Party (2-sat)

題目地址：HDU 3062

2-sat第一發。水題。。

首先假設A，A'為同一組的兩個布爾變量且不能同時選擇同一組的兩個變量。如果存在一種同時選擇了A和A'的方案，則該方案無解。
設為選擇X就必須選擇Y，則基本的建圖如下：
A，B不能同時選：，表示選擇A就必須不能選擇B，選擇B就不能選擇A
A，B不能同時不選：，表示不選A則必須選B，不選B則必須選A
A，B必須同時選或同時不選：，略。。

對這題來說，夫妻就是同一組的兩個布爾變量，然後給出了一些矛盾關系，根據這些矛盾關系加邊，然後判斷是否有一組的布爾變量在同一塊強連通分量中，如果在同一塊，那就說明產生了矛盾，無解。

代碼如下：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;
#define LL __int64
const int INF=0x3f3f3f3f;
int dfn[2100], low[2100], belong[2100], instack[2100], stak[2100];
int head[2100], cnt, index, top, ans;
struct node
{
    int u, v, next;
}edge[100000];
void add(int u, int v)
{
    edge[cnt].v=v;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}
void init()
{
    memset(dfn,0,sizeof(dfn));
    memset(instack,0,sizeof(instack));
    memset(head,-1,sizeof(head));
    cnt=0;
    index=top=ans=0;
}
void tarjan(int u)
{
    dfn[u]=low[u]=++index;
    stak[++top]=u;
    instack[u]=1;
    for(int i=head[u];i!=-1;i=edge[i].next)
    {
        int v=edge[i].v;
        if(!dfn[v])
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(instack[v])
        {
            low[u]=min(dfn[v],low[u]);
        }
    }
    if(low[u]==dfn[u])
    {
        ans++;
        while(1)
        {
            int v=stak[top--];
            instack[v]=0;
            belong[v]=ans;
            if(u==v) break;
        }
    }
}
int main()
{
	int n, m, i, a1, a2, c1, c2, j, flag;
	while(scanf("%d%d",&n,&m)!=EOF)
    {
        init();
        while(m--)
        {
            scanf("%d%d%d%d",&a1,&a2,&c1,&c2);
            add(2*a1+c1,2*a2+1-c2);
            add(2*a2+c2,2*a1+1-c1);
        }
        for(i=0;i<2*n;i++)
        {
            if(!dfn[i])
                tarjan(i);
        }
        flag=0;
        for(i=0;i