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   
#include   
#include   
#include   
 
#include   
#include   
#include   
#include   
#include   
 
#include   
#include   
#include   
#include   
#include   
#include   
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 vi; 
typedef stack si; 
typedef vector 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 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::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
#include 
#include 
#include 

#include 
#include 
#include 
#include 
#include 

#include 
#include 
#include 
#include 
#include 
#include 
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 vi;
typedef stack si;
typedef vector 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 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::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