当前位置:首页 > 搜索 > 深度优先搜索 > 正文
SSOJ2366部落卫队
2178+

题目大意:从n个居民里选出最多的互不发生冲突的人加入保卫部落的队伍,已知居民的冲突关系,如果选人?

题目描述

原始部落byteland中的居民们为了争夺有限的资源,经常发生冲突。几乎每个居民都有他的仇敌。部落酋长为了组织一支保卫部落的队伍,希望从部落的居民中选出最多的居民入伍,并保证队伍中任何2个人都不是仇敌。

编程任务:

给定byteland部落中居民间的仇敌关系,编程计算组成部落卫队的最佳方案。

输入

第一行有2个正整数n和m,表示byteland部落中有n个居民,居民间有m个仇敌关系。居民编号1,2,3…,n。接下来的m行中,每行有2个正整数u和v,表示居民u与居民v是仇敌。

输出

第一行是部落卫队的总人数;第二行是卫队组成xi,1<=i<=n,xi=0表示居民i不在卫队中,xi=1表示居民i在卫队中。

样例输入

7 10
1 2
1 4
2 4
2 3
2 5
2 6
3 5
3 6
4 5
5 6

样例输出

3
1 0 1 0 0 0 1

解题思路

n个格子,要么填0,要么填1。随时都可以填0,填1的话需要判断是否与前面冲突。填完后,记录最多1的个数,以及填法。

可行性剪枝:如果想选第k个人,就必须扫描前面k-1个人,其中选了的人不能与第k个人发生冲突。(必须,不然最后才判断是否可行,2的100次方中方案会超时)

最优性剪枝:如果选了s个人,还剩下n-k+1个人还没确定选不选,但s+n-k+1不大于(<=)ans,那么后面就不会更好、不用看了。(本题不写也可以过,但很多题目最优性剪枝能大大提高速度)

程序实现

SSOJ2366部落卫队:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!