Problem 1412 --算法实现题 5-21 部落卫队问题（习题 5-6）1412: 算法实现题 5-21 部落卫队问题（习题 5-6）
| Time Limit |
$1$ 秒/Second(s) |
Memory Limit |
$512$ 兆字节/Megabyte(s) |
| 提交总数 |
$96$ |
正确数量 |
$9$ |
"
| 裁判形式 |
标准裁判/Standard Judge |
我的状态 |
尚未尝试 |
| 难度 |
|
分类标签 |
回溯 |
当前分类(单击移除)：
回溯
单击选择分类：
原始部落 byteland 中的居民们为了争夺有限的资源，经常发生冲突。几乎每个居民都有他的仇敌。部落酋长为了组织一支保卫部落的队伍，希望从部落的居民中选出最多的居民入伍，并保证队伍中任何 2 个人都不是仇敌。
«算法设计：
给定 byteland 部落中居民间的仇敌关系，计算组成部落卫队的最佳方案。
输入第 1 行有 2 个正整数 n 和 m，表示 byteland 部落中有 n个居民，居民间有 m 个仇敌关系。居民编号为 1，2，…，n。接下来的 m 行中，每行有 2个正整数 u 和 v，表示居民 u 与居民 v 是仇敌。
将计算出的部落卫队的最佳组建方案输出。第 1 行是部落卫队的顶人数；文件的第 2 行是卫队组成 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
| 本题记录 |
用 户（点击查看用户） |
运行号（点击购买题解） |
时 间 |
| 算法最快[$94 $ms]
|
月落星辰挽
|
842402
|
2022-04-16 16:33:47 |
| 内存最少[$2176 $KB]
|
月落星辰挽
|
842420 |
2022-04-16 16:42:41 |
| 第一AC |
张利峰 |
252007
|
2018-05-27 18:19:48 |
| 第一挑战 |
卑微小赵
|
220448 |
2018-04-08 00:57:39 |
| 竞赛编号 |
竞赛名称 |
竞赛时间 |
访问比赛 |
| 1149 |
2017-2018-2《C语言程序设计II》课下练习@2017计算机科学与技术123 |
2018-03-06 12:00:00 |
请登录
|