第一课堂
Current course
Participants
General
50道示题
Topic 3
Topic 4
Topic 5
Topic 6
Topic 7
Topic 8
Topic 9
Topic 10
Topic 11
Topic 12
Topic 13
Topic 14
Topic 15
Topic 16
Topic 17
Topic 18
Topic 19
Topic 20
[NERRC 2006][POJ3155]生活的艰辛
Grade | Open Time | Friday, 19 September 2014, 10:08 am | |
Discount | 0.8 | Time Discount | Friday, 26 September 2014, 10:08 am |
Allow late | Yes | Close Time | Friday, 26 September 2014, 10:08 am |
Input file | hardlife.in | Output file | hardlife.out |
【题目描述】
John是一家中等规模私有企业的CEO。公司的老板决定让他的儿子Scott做公司经理。John害怕如果Scott干的漂亮,老板就会让他夺走自己的职位,因此他决定仔细挑选Scott将要管理的团队来让这位新经理的人生尽量艰难……
John知道他手下的哪些人之间有大仇,导致这两个人在同一团队干活时会非常捉急。John为一个团队定义了一个艰难系数,即大仇的总数除以人数。显然艰难系数越大这个团队就越难管理。John希望找到一组最难管理的员工作为Scott的团队。请帮助他。
图中展示了一个例子,最难管理的团队包含了编号为1,2,4,5的人。在这四个人中有五对人有大仇,因此艰难系数就是5/4.如果我们把3加进去,艰难系数就变成了6/5.
【输入格式】
输入文件的第一行包含了两个整数n,m(1<=n<=100,0<=m<=1000).这里n是员工总数(员工从1到n编号),m是大仇的数量。
接下来的m行每行包含两个整数ai,bi(1<=ai,bi<=n,ai≠bi),表示ai,bi之间有大仇。同一对人不会出现两次。
【输出格式】
先输出一个正整数k(1<=k<=n),即最难管理的团队人数。接下来有k行每行一个整数,它们按递增顺序给出了最难管理的团队中的人员编号。
如果有多组解,输出任意一组。
【样例输入】
sample input #1
5 6
1 5
5 4
4 2
2 5
1 2
3 1
sample input #2
4 0
【样例输出】
sample output #1
4
1
2
4
5
sample output #2
1
1
【提示】
(原注:在第二个样例中,没有人之间有大仇,即艰难系数为零。因此任意一个非空集合都是合法的。)
由于没有评测插件,在遇到这种情况时请输出一个仅有1号员工的集合,就像样例2一样。
【来源】
Northeastern Europe 2006(NEERC 2006)