Welcome   HUNAN NORMAL UNIVERSITY ACM/ICPC Judge Online
Home
FAQs
Problem Set
Practices
Online Contests
Major Exercises
OI Special
Judgement
Submit
Online Status
User Ranklist
Users
Register new
Login
Web Links
Hunan Normal University
College of Mathematics and Computer Science
最小权顶点覆盖问题
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:65536KB
Total submit users: 8, Accepted users: 6
Problem 10349 : No special judgement
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
Submit   Clarifications   Judge Status  Problems  Ranklist 

HUNAN NORMAL UNIVERSITY ACM/ICPC Judge Online, Version 2010.5.5.final.
Web visits:697 today,10665911 total, since 2010-05-07