当前位置:首页 > 图论 > 强连通 > 正文
SSOJ2799和平委员会
79+

题目大意:n个党派,每个党派有2人,有m个冲突关系,选出n个人,要求每个党派各1人,且无冲突,输出一种方案。

题目描述

原题来自:POI 2001

根据宪法,Byteland 民主共和国的公众和平委员会应该在国会中通过立法程序来创立。 不幸的是,由于某些党派代表之间的不和睦而使得这件事存在障碍。

此委员会必须满足下列条件:

  • 每个党派都在委员会中恰有 1 个代表,
  • 如果 2 个代表彼此厌恶,则他们不能都属于委员会。

每个党在议会中有 2 个代表。代表从 1 编号到 2n。 编号为 2i12i 的代表属于第 i 个党派。

任务:写一程序读入党派的数量和关系不友好的代表对,计算决定建立和平委员会是否可能,若行,则列出委员会的成员表。

输入

第一行有两个非负整数 nm。他们各自表示:党派的数量 n 和不友好的代表对 m。 接下来 m 行,每行为一对整数 a,b,表示代表 a,b 互相厌恶。

输出

如果不能创立委员会,则输出信息NIE。若能够成立,则输出包括 n 个从区间 12n 选出的整数,按升序写出,每行一个,这些数字为委员会中代表的编号。

如果委员会能以多种方法形成,程序可以只输出它们的某一个。

提示

样例输入

3 2
1 3
2 4

样例输出

1
4
5

1≤n≤8000,0≤m≤20000,1≤a < b≤2n

解题思路

如果两个人a和b有冲突,那么选a就不能选b,又要求每个党派都要选,那么只能选b党派中的另外一个人。

按照必选关系建图,缩点后,如果同一个党派的两人在一个集合,那么两人都选或都不选,不能达到n人每个党派各一人,无解。

对于有解情况,输出缩点后的DAG中拓扑序大的点即可。

提示1:2-SAT的图是对称了。

提示2:一个党派的两人,在DAG上,如果选择拓扑序大的显然不可行,应该选择拓扑序小的。

程序实现

About

坚决不Copy代码!

本文标签:,,,,,,

SSOJ2799和平委员会:等您坐沙发呢!

发表评论

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

快捷键:Ctrl+Enter