hdu-3062

Party
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 5259 Accepted Submission(s): 1698
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题。主要难点在于建图。每一种情况都用点表示。由这些情况可以得出以下关系。 
    
   
     假设第i对夫妻Ai(妻子），Ai'（丈夫）； 
    
   
     Ai-〉！Ai’ 
    
   
     ！Ai-〉Ai' 
    
   
     Ai'->！Ai 
    
   
     ！Ai'->Ai 
    
    
    
    
    第j对夫妻Aj（妻子），Aj'（丈夫）与第i对夫妻有矛盾；假设Ai与Aj有矛盾。 
    
    
    Ai-〉！Aj 
    
    
    Aj-〉！Ai 
    
    
    接着只要将这种关系用边表示就行了。 
    
   
     如果Ai与！Ai（i为任何一个人）同时在一个强连通分量之 
    中，那么就矛盾输出NO，否则为（YES） 
    
    
    
    
    
   
     代码如下： 
    
    
    
    
    #include
#include
#include
#include
#include
#define MAXN 4000+100
#define MAXM 2000000+5000
#define INF 10000000
using namespace std;
struct stu
{
	int f,t,ne;
};
stu edge[MAXM];
int head[MAXN];
int dfn[MAXN];
int low[MAXN];
int instack[MAXN];
int scc_on[MAXN];
int num,n,m,scc,s_clock;
stackS;
void inin()
{
    num=0;
    memset(head,-1,sizeof(head));
}
void add(int a,int b)
{
    stu E={a,b,head[a]};
    edge[num]=E;
    head[a]=num++;
}
void get_map()
{
    for(int i=0;i

hdu-3062

좋은 웹페이지 즐겨찾기