Problem 1419 --算法实现题 6-3 最小权顶点覆盖问题（习题 6-10）1419: 算法实现题 6-3 最小权顶点覆盖问题（习题 6-10）
| Time Limit |
$1$ 秒/Second(s) |
Memory Limit |
$512$ 兆字节/Megabyte(s) |
| 提交总数 |
$1$ |
正确数量 |
$0$ |
"
| 裁判形式 |
标准裁判/Standard Judge |
我的状态 |
尚未尝试 |
| 难度 |
|
分类标签 |
图论 |
当前分类(单击移除)：
图论
单击选择分类：
给定一个赋权无向图 G=(V,E)，每个顶点 v∈V 都有一个权值 w(v)。如果 U包含于V，且对任意(u,v)∈E 有 u∈U 或 v∈U，就称 U 为图 G 的一个顶点覆盖。G 的最小权顶点覆盖是指 G中所含顶点权之和最小的顶点覆盖。
«算法设计：
对于给定的无向图 G，设计一个优先队列式分支限界法，计算 G 的最小权顶点覆盖。
输入第 1 行有 2 个正整数 n 和 m，表示给定的图 G 有 n 个顶点和 m 条边，顶点编号为 1，2，…，n。第 2 行有 n 个正整数表示 n 个顶点的权。接下来的 m 行中，每行有 2 个正整数 u,v，表示图 G 的一条边(u,v)。
将计算出的最小权顶点覆盖的顶点权之和以及最优解输出。第 1 行是最小权顶点覆盖顶点权之和；第 2 行是最优解 xi ,1 <= i <= n ， xi =0 表示顶点 i不在最小权顶点覆盖中, xi =1 表示顶点 i 在最小权顶点覆盖中。
7 7
1 100 1 1 1 100 10
1 6
2 4
2 5
3 6
4 5
4 6
6 7
| 本题记录 |
用 户（点击查看用户） |
运行号（点击购买题解） |
时 间 |
| 算法最快[$ $ms]
|
|
|
|
| 内存最少[$ $KB]
|
|
|
|
| 第一AC |
|
|
|
| 第一挑战 |
AOJ大管家
|
259281 |
2018-06-05 02:08:23 |