当前位置:首页 > 图论 > 强连通 > 正文
HDU3062Party
739+

题目大意:n对夫妻参加聚会,人数有限只能派一人做代表,这2n人中,有些存在矛盾,不能同时出席,请问能否做得没对夫妻都派出1人参加聚会且不发生冲突。

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

解题思路

只需要判断是否可行,缩点后判断一对夫妻是否在同一个集合即可。

存储:妻子编号1到n,丈夫编号n+1到n+n。x和y有冲突,那么x只能和y+n搭配,y只能和x+n搭配;x和y+n有冲突,那么x只能和y搭配,y+n只能和x+n搭配。什么时候加n?异或关系!

建图后,缩点,如果同一对夫妻在一个集合,要么都去,要么都不去,不可能做得n个人n对夫妻都包含。

程序实现

About

坚决不Copy代码!

本文标签:,,,,

HDU3062Party:等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter