首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。