Problem description
给定一个赋权无向图G=(V,E),每个顶点v∈V都有
2016-08-22
2 0 0
暂无评分
其他
如何获取积分?
Problem description
给定一个赋权无向图G=(V,E),每个顶点v∈V都有一个权值w(v)。如果U包含于V,且对于(u,v)∈E 有u∈U 且v∈V-U,则有v∈K.如:U = {1}, 若有边(1,2), 则有2属于K. 若有集合U包含于V使得U + K = V, 就称U 为图G 的一个顶点覆盖。G 的最小权顶点覆盖是指G 中所含顶点权之和最小的顶点覆盖。
Input
输入数据。第1 行有2 个正整数n 和m,表示给定的图G 有n 个顶点和m条边,顶点编号为1,2,…,n。第2 行有n个正整数表示n个顶点的权。接下来的m行中,每行有2 个正整数u,v,表示图G 的一条边(u,v)。
Output
将计算出的最小权顶点覆盖的顶点权之和输出。
Sample Input
7 7
1 100 1 1 1 100 10
1 6
2 4
2 5
3 6
4 5
4 6
6 7
Sample Output
13
-Problem description
给定一个赋权无向图G=(V,E),每个顶点v∈V都有一个权值w(v)。如果U包含于V,且对于(u,v)∈E 有u∈U 且v∈V-U,则有v∈K.如:U = {1}, 若有边(1,2), 则有2属于K. 若有集合U包含于V使得U+ K = V, 就称U 为图G 的一个顶点覆盖。G 的最小权顶点覆盖是指G 中所含顶点权之和最小的顶点覆盖。
Input
输入数据。第1 行有2 个正整数n 和m,表示给定的图G 有n 个顶点和m条边,顶点编号为1,2,…,n。第2 行有n个正整数表示n个顶点的权。接下来的m行中,每行有2 个正整数u,v,表示图G 的一条边(u,v)。
Output
将计算出的最小权顶点覆盖的顶点权之和输出。
Sample Input
7 7
1 100 1 1 1 100 10
1 6
2 4
2 5
3 6
4 5
4 6
6 7
Sample Output
13
相关源码推荐
使用Java开发Android AOA Android开放式附件
0
0
暂无评分
Golang AOA Android开放式附件HID控制
0
0
暂无评分
pclite
0
0
暂无评分
GMSK线性接收机
0
0
暂无评分
传世AFT中变打金版版本--以前很火爆的,收藏很久
0
0
暂无评分
暂无评论