首页 > 代码库 > XTU 1252 Defense Tower

XTU 1252 Defense Tower

$2016$长城信息杯中国大学生程序设计竞赛中南邀请赛$J$题

贪心。

优先删除$power$大的点。

#pragma comment(linker, "/STACK:1024000000,1024000000")#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<vector>#include<map>#include<set>#include<queue>#include<stack>#include<iostream>using namespace std;typedef long long LL;const double pi=acos(-1.0),eps=1e-8;const int maxn=100010;int p[maxn],n;vector<int>g[maxn];struct X { int h,p; }s[maxn];bool f[maxn];bool cmp(X a,X b) {return a.p>b.p;}int main(){    while(~scanf("%d",&n))    {        for(int i=1;i<=n;i++)        {            scanf("%d",&s[i].p), s[i].h=i;            p[i]=s[i].p;        }        sort(s+1,s+1+n,cmp); memset(f,0,sizeof f);        for(int i=1;i<=n;i++) g[i].clear();        for(int i=1;i<=n-1;i++)        {            int a,b; scanf("%d%d",&a,&b);            g[a].push_back(b); g[b].push_back(a);        }        LL ans=0;        for(int i=1;i<=n;i++)        {            for(int j=0;j<g[s[i].h].size();j++)            {                int to=g[s[i].h][j];                if(f[to]) continue;                ans=ans+(LL)p[to];            }            f[s[i].h]=1;        }        cout<<ans<<endl;    }    return 0;}

 

XTU 1252 Defense Tower