首页| JavaScript| HTML/CSS| Matlab| PHP| Python| Java| C/C++/VC++| C#| ASP| 其他|
购买积分 购买会员 激活码充值

您现在的位置是:虫虫源码 > C# > Problem description 给定一个赋权无向图G=(V,E),每个顶点v∈V都有一个权值w(v)。如果U包含于V,且对于(u,v)∈E 有u...

Problem description 给定一个赋权无向图G=(V,E),每个顶点v∈V都有一个权值w(v)。如果U包含于V,且对于(u,v)∈E 有u...

  • 资源大小:211.82 kB
  • 上传时间:2021-06-29
  • 下载次数:0次
  • 浏览次数:1次
  • 资源积分:1积分
  • 标      签: C#

资 源 简 介

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

文 件 列 表

最小权顶点覆盖问题
Debug
input.txt
MinCover.cpp
MinCover.dsp
MinCover.dsw
MinCover.ncb
MinCover.opt
MinCover.plg
MinHeap.h

相 关 资 源

您 可 能 感 兴 趣 的

同 类 别 推 荐

VIP VIP
0.270990s