当前位置:首页 > 瞎暴力 > 2016湘潭邀请赛 xtu 1252 Defense Tower

2016湘潭邀请赛 xtu 1252 Defense Tower

In ICPCCamp, there arencities and(n1)(bidirectional) roads between cities. Thei-th road is between theai-th andbi-th cities. It is guaranteed that cities are connected.

In thei-th city, there is a defense tower with powerpi. The tower protects all cities with a road directly connected to cityi. However, the tower in cityidoes not protect cityiitself.

Bobo would like to destroy all defense towers. When he tries to destroy the tower in cityi, any not-destroyed tower protecting cityiwill 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 most30sets. For each set:

The first line contains an integern(1n105).

The second line containsnintegersp1,p2,,pn(1pi104).

Thei-th of the last(n1)lines contains2integersai,bi(1ai,bin).

Output

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

Sample Input

3
1 2 3
1 2
2 3
3
1 100 1
1 2
2 3

Sample Output

3
2

直接干。。。本来是弄边权值和最大的 但是想一下 把攻击力最高的去掉就好了

#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
#include<vector>
using namespace std;

struct p
{
    int num,val;
    friend bool operator<(p a,p b)
    {
        return a.val<b.val;
    }
}df[100005];
vector<int>edge[100005];

int main()
{
    int n,x,y,ans;
    int vis[100005];
    while(~scanf("%d",&n))
    {
        for(int i=0;i<=n;i++)
            edge[i].clear();
        priority_queue<p>q;
        memset(vis,0,sizeof vis);
        for(int i=1;i<=n;i++)
        {
            df[i].num=i;
            scanf("%d",&df[i].val);
            q.push(df[i]);
        }
        for(int i=1;i<=n-1;i++)
        {
            scanf("%d %d",&x,&y);
            edge[x].push_back(y);
            edge[y].push_back(x);
        }
        ans=0;
        while(!q.empty())
        {
            int v=q.top().num;
            for(int i=0;i<edge[v].size();i++)
            {
                if(vis[edge[v][i]]==0)
                    ans+=df[edge[v][i]].val;
            }
            vis[v]=1;
            q.pop();
        }
        printf("%d\n",ans);
    }
}


除特别注明外,本站所有文章均为whppmy原创,转载请注明出处来自http://www.dengwenhuo.cn/?id=200

发表评论

  •  访客
     发布于 2016-06-30 21:58:55  回复该评论
  • 博主,你这代码交上去超时啊.
    •  dwh
       发布于 2016-07-06 10:57:17  回复该评论
    • 多谢提醒 copy的时候自己减了一行代码 1700ms左右就能过的

发表评论:

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。