主题

主题

 
   

Party

原题:http://acm.hdu.edu.cn/showproblem.php?pid=3062

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


个人解法:

(终于看到少许不是英文题的)

首先问题包含着一个条件,每对夫妻中必须要有一个人出席。(否则建图的逻辑就不成立了)

然后每队夫妻拆点。

限制很简单,举个例子:

如果A[0]与B[1]有矛盾,那么A[0]->B[0],B[1]->A[1]。

跑Tarjan即可。


代码如下:

https://code.csdn.net/snippets/2298258

 
 
评论