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

HDU 3062 Party 2-SAT 入門題

編輯：C++入門知識

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

Source
2009 Multi-University Training Contest 16 - Host by NIT

Recommend
lcy

由於題目問題。知道n對夫妻要上N個人。也就是每對夫妻出一個人。

可以這麼說。給出一條矛盾關系
如果是 i,j,0,0 ，可以連有向邊 i0->j1,j0->i1 若出來i0，則必須出來j1.類推
如果是 i,j,0,1 , 可以連有向邊 i0->j0,j1->i1
如果是 i,j,1,0 , 可以連有向邊 i1->j1,j0->i0
如果是 i,j,1,1 , 可以連有向邊 i1->j0,j1->i0

如此就建好了一個所有有約束關系的有向圖了，由於只是一個判定性問題，只需在這樣建立的有向圖上運行一次強連通算法，最後再判定所有的i0,j0是否存在於一個強連通分量即可。

 /*
 * @author ipqhjjybj
 * @date  20130702
 *
 */ 
 
#include <cstdio>  
#include <cmath>  
#include <cstdlib>  
#include <ctime>  
 
#include <iostream>  
#include <cmath>  
#include <algorithm>  
#include <numeric>  
#include <utility>  
 
#include <cstring>  
#include <vector>  
#include <stack>  
#include <queue>  
#include <map>  
#include <string>  
using namespace std; 
 
#define inf 0x3f3f3f3f  
#define MAXN 2005  
#define clr(x,k) memset((x),(k),sizeof(x))  
#define clrn(x,k) memset((x),(k),(n+1)*sizeof(int))  
#define cpy(x,k) memcpy((x),(k),sizeof(x))  
#define Base 10000  
 
typedef vector<int> vi; 
typedef stack<int> si; 
typedef vector<string> vs; 
#define sz(a) int((a).size())  
#define pb push_back  
#define all(c) (c).begin(),(c).end()  
#define rep(i,n) for(int i = 0;i < n;++i)  
#define foreach(it,c) for(vi::iterator it = (c).begin();it != (c).end();++it)  
 
#define max(a,b) ((a)>(b)?(a):(b))  
#define min(a,b) ((a)<(b)?(a):(b))  
 
vector<int> vec[MAXN]; 
int n,m; 
int id[MAXN],pre[MAXN],low[MAXN],s[MAXN],stop,cnt,scnt; 
void init(){ 
    int u,v; 
    for(int i = 0;i < n+n;i++) vec[i].clear(); 
    for(int i = 0,a,b,c,d;i < m;i++){ 
        scanf("%d %d %d %d",&a,&b,&c,&d); 
        u = (a<<1) + c ;  v = (b<<1) + d; 
        vec[u].push_back(v^1); 
        vec[v].push_back(u^1); 
    } 
    stop=cnt=scnt=0; 
    clr(pre,-1); 
    clr(id,0); 
} 
void Tarjan(int v,int n){ 
    int t,minc=low[v]=pre[v]=cnt++; 
    vector<int>::iterator pv; 
    s[stop++]=v; 
    for(pv=vec[v].begin();pv!=vec[v].end();++pv){ 
        if(-1==pre[*pv]) Tarjan(*pv,n); 
        if(low[*pv] < minc) minc=low[*pv]; 
    } 
    if(minc<low[v]){ 
        low[v]=minc;return; 
    }do{ 
        id[t=s[--stop]]=scnt;low[t]=n; 
    }while(t!=v); 
    ++scnt; 
} 
int main(){ 
   // freopen("3062.in","r",stdin);  
    int i; 
    while(scanf("%d",&n)!=EOF&&n){ 
        scanf("%d",&m); 
        init(); 
        for(i = 0;i < n+n;i++) 
            if(-1==pre[i]) 
                Tarjan(i,n+n); 
        //以下進行判斷  
        bool flag = true; 
        for(i=0;i<n;i++) 
            if(id[i<<1]==id[(i<<1)^1]){ 
                  flag=false; 
                  break; 
            } 
        if(flag) 
            printf("YES\n"); 
        else printf("NO\n"); 
    } 
    return 0; 
} 

/*
 * @author ipqhjjybj
 * @date  20130702
 *
 */

#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

#include <iostream>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <utility>

#include <cstring>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <string>
using namespace std;

#define inf 0x3f3f3f3f
#define MAXN 2005
#define clr(x,k) memset((x),(k),sizeof(x))
#define clrn(x,k) memset((x),(k),(n+1)*sizeof(int))
#define cpy(x,k) memcpy((x),(k),sizeof(x))
#define Base 10000

typedef vector<int> vi;
typedef stack<int> si;
typedef vector<string> vs;
#define sz(a) int((a).size())
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define rep(i,n) for(int i = 0;i < n;++i)
#define foreach(it,c) for(vi::iterator it = (c).begin();it != (c).end();++it)

#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))

vector<int> vec[MAXN];
int n,m;
int id[MAXN],pre[MAXN],low[MAXN],s[MAXN],stop,cnt,scnt;
void init(){
    int u,v;
    for(int i = 0;i < n+n;i++) vec[i].clear();
    for(int i = 0,a,b,c,d;i < m;i++){
        scanf("%d %d %d %d",&a,&b,&c,&d);
        u = (a<<1) + c ;  v = (b<<1) + d;
        vec[u].push_back(v^1);
        vec[v].push_back(u^1);
    }
    stop=cnt=scnt=0;
    clr(pre,-1);
    clr(id,0);
}
void Tarjan(int v,int n){
    int t,minc=low[v]=pre[v]=cnt++;
    vector<int>::iterator pv;
    s[stop++]=v;
    for(pv=vec[v].begin();pv!=vec[v].end();++pv){
        if(-1==pre[*pv]) Tarjan(*pv,n);
        if(low[*pv] < minc) minc=low[*pv];
    }
    if(minc<low[v]){
        low[v]=minc;return;
    }do{
        id[t=s[--stop]]=scnt;low[t]=n;
    }while(t!=v);
    ++scnt;
}
int main(){
   // freopen("3062.in","r",stdin);
    int i;
    while(scanf("%d",&n)!=EOF&&n){
        scanf("%d",&m);
        init();
        for(i = 0;i < n+n;i++)
            if(-1==pre[i])
                Tarjan(i,n+n);
        //以下進行判斷
        bool flag = true;
        for(i=0;i<n;i++)
            if(id[i<<1]==id[(i<<1)^1]){
                  flag=false;
                  break;
            }
        if(flag)
            printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}