HDU3062 - 2-sat

阳光穿透心脏的1/2处 2022-07-16 16:26 113阅读 0赞

# Party #

**Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 6168    Accepted Submission(s): 2013**

Problem Description

有n对夫妻被邀请参加一个聚会，因为场地的问题，每对夫妻中只有1人可以列席。在2n 个人中，某些人之间有着很大的矛盾（当然夫妻之间是没有矛盾的），有矛盾的2个人是不会同时出现在聚会上的。有没有可能会有n 个人同时列席？

Input

n： 表示有n对夫妻被邀请 (n<= 1000)  
m： 表示有m 对矛盾关系 ( m < (n - 1) \* (n -1))  
  
在接下来的m行中，每行会有4个数字，分别是 A1,A2,C1,C2   
A1,A2分别表示是夫妻的编号   
C1,C2 表示是妻子还是丈夫 ，0表示妻子 ，1是丈夫  
夫妻编号从 0 到 n -1

Output

如果存在一种情况 则输出YES   
否则输出 NO

Sample Input

2 
    1
    0 1 1 1

Sample Output

YES

**题目大意：**

2-sat问题，详见博客：[浅谈 2-SAT问题][2-SAT]

**题目思路**：

对于这类问题一般的解法为将每个点分为 x 和 x' 分别表示每组当中的两种状态，这里表示丈夫和妻子，然后更具定义我们建图，如果 A和B有矛盾则选A必选B'，选B必选A' ，所以我们对该图缩点，如果A和A'属于同一个环当中则说明选A必选A'，所以不存在，否则就存在

**AC代码：**

#include<cstring>
    #include<cstdio>
    
    const int maxn = 3e3+20;
    
    int low[maxn],dfn[maxn],vis[maxn],belon[maxn],stack[maxn];
    
    int hed[maxn];
    
    int n,m,e,top,cnt,num;
    
    struct st{
        int v,nex;
    }edge[maxn*maxn];
    
    void add(int u,int v){
        edge[e].v=v,edge[e].nex=hed[u],hed[u]=e++;
    }
    
    void init(){
        memset(dfn,0,sizeof(dfn));
        memset(vis,0,sizeof(vis));
        memset(hed,-1,sizeof(hed));
        memset(belon,0,sizeof(belon));
        e=num=cnt=top=0;
    }
    
    void targan(int u){     //targan缩点
        low[u]=dfn[u]=++num;
        stack[top++]=u;
        vis[u]=1;
        for(int i=hed[u];~i;i=edge[i].nex){
            int v = edge[i].v;
            if(!dfn[v]){
                targan(v);
                if(low[u]>low[v])low[u]=low[v];
            }else if(vis[v]&&dfn[v]<low[u])low[u]=dfn[v];
        }
        if(low[u]==dfn[u]){
            int x;
            ++cnt;
            do{
                x =stack[--top];
                vis[x]=0;
                belon[x]=cnt;
            }while(x!=u);
        }
    }
    
    bool work(){
        for(int i=0;i<2*n;i++)if(!dfn[i])targan(i);
        for(int i=0;i<n;i++){
            if(belon[i*2]==belon[i*2+1])return false;   //同一组的成环
        }
        return true;
    }
    
    int main()
    {
        while(~scanf("%d",&n)){
                scanf("%d",&m);
                init();
                for(int i=0;i<m;i++){
                    int a,b,c,d;scanf("%d%d%d%d",&a,&b,&c,&d);
                    a = a*2+c;
                    b = b*2+d;
                    add(a,b^1);     //选A必选B'
                    add(b,a^1);     //选B必选A'
                }
                if(work())printf("YES\n");
                else printf("NO\n");
        }
        return 0;
    }

[2-SAT]: http://blog.csdn.net/pi9nc/article/details/11849843