xtu 1252

1252

Defense Tower

In ICPCCamp, there are cities and (bidirectional) roads between cities. The -th road is between the -th and -th cities. It is guaranteed that cities are connected.

In the -th city, there is a defense tower with power . The tower protects all cities with a road directly connected to city . However, the tower in city does not protect city itself.

Bobo would like to destroy all defense towers. When he tries to destroy the tower in city , any not-destroyed tower protecting city will deal damage whose value equals to its power to Bobo.

Find out the minimum total damage Bobo will receive if he chooses the order to destroy the towers optimally.

Input

The input contains at most sets. For each set:

The first line contains an integer ().

The second line contains integers ().

The -th of the last lines contains integers ().

Output

For each set, an integer denotes the minimum total damage.

Sample Input

Sample Output

3
2

湘潭去年比赛的题目，与我们最开始想的题目的类型都不同，我们最开始以为是模拟题，不知道怎么模拟，然后做不了，其实这是个贪心的题目
题意：就是在每个城市有个防御塔，这个塔有攻击力，可以保护与这个城市相连的其他城市，但是不能保护自己，求要破坏所有的塔所受最少的伤害
思路：就是贪心，用优先队列，每次取伤害最高的塔所在的城市，攻击这个城市，然后把与其相连的城市的攻击力加起来。

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <queue>
 4 #include <vector>
 5 
 6 using namespace std;
 7 
 8 vector<int >edge[100005];
 9 
10 struct node{
11     int a,b;
12      friend bool operator<(node a,node b)
13     {
14         return a.b<b.b;
15     }
16 }pow[100005];
17 
18 
19 priority_queue<node>s;
20 
21 int main()
22 {
23     int n,a,b,ans;
24     node tmp;
25     bool flag[100005];
26     while(~scanf("%d",&n))
27     {
28         memset(flag,true,sizeof(flag));
29         for(int i = 1;i<=n;i++)
30             edge[i].clear();
31         ans = 0;
32         for(int i = 1;i<=n;i++)
33         {
34             pow[i].a = i;
35             scanf("%d",&pow[i].b);
36             s.push(pow[i]);
37         }
38         for(int i = 1;i<n;i++)
39         {
40             scanf("%d%d",&a,&b);
41             edge[a].push_back(b);
42             edge[b].push_back(a);
43         }
44         while(!s.empty())
45         {
46             tmp = s.top();
47             for(int i =0;i<edge[tmp.a].size();i++)
48             {
49                     if(flag[edge[tmp.a][i]])
50                     {
51                         ans+=pow[edge[tmp.a][i]].b;
52                     }
53             }
54             flag[tmp.a] = false;
55             s.pop();
56         }
57         printf("%d
",ans);
58     }
59     return 0;
60 }