level 1
大扫比
楼主
用回溯算法
部落卫队问题
1
、
问题描述;
原始部落
byteland
中的居民们为了争夺有限的资源,
经常发生冲
突。
几乎每个居民都有他的仇敌。
部落酋长为了组织一支保卫部落的队伍,
希望
从部落的居民中选出最多的居民入伍,并保证队伍中任何
2
个人都不是仇敌。
2
、
算法设计;
给定
byteland
部落中居民间的仇敌关系,
计算组成部落卫队的最
佳方案
3
、数据输入;由文件
input.txt
给出输入数据。第一行有两个正整数
n
和
m
,
表示
byteland
部落中有
n
个居民,
居民间有
m
个仇敌关系。
居民编号为
1
,
2
,
…,n。
接下来的
m
行中,每行有
2
个正整数
u
和
v
,表示居民
u
和
v
是仇敌
4
、结果输出;将计算的部落卫队的最佳方案输出到文件
output.txt
。文件的第
一行是部落卫队的人数;第二行是部落卫队组成
Xi
,1≤i≤n。
Xi=0
表示居民
i
不在卫队中,
Xi=1
表示居民在卫队中
2014年12月20日 09点12分
1
部落卫队问题
1
、
问题描述;
原始部落
byteland
中的居民们为了争夺有限的资源,
经常发生冲
突。
几乎每个居民都有他的仇敌。
部落酋长为了组织一支保卫部落的队伍,
希望
从部落的居民中选出最多的居民入伍,并保证队伍中任何
2
个人都不是仇敌。
2
、
算法设计;
给定
byteland
部落中居民间的仇敌关系,
计算组成部落卫队的最
佳方案
3
、数据输入;由文件
input.txt
给出输入数据。第一行有两个正整数
n
和
m
,
表示
byteland
部落中有
n
个居民,
居民间有
m
个仇敌关系。
居民编号为
1
,
2
,
…,n。
接下来的
m
行中,每行有
2
个正整数
u
和
v
,表示居民
u
和
v
是仇敌
4
、结果输出;将计算的部落卫队的最佳方案输出到文件
output.txt
。文件的第
一行是部落卫队的人数;第二行是部落卫队组成
Xi
,1≤i≤n。
Xi=0
表示居民
i
不在卫队中,
Xi=1
表示居民在卫队中