首页
学习
活动
专区
工具
TVP
发布

hdu1055

作者头像
@坤的
发布2018-06-04 11:15:46
3680
发布2018-06-04 11:15:46
举报
文章被收录于专栏:*坤的Blog*坤的Blog

#include<iostream> #include<iomanip> #include<cstdio> #include<cstring> #include<algorithm> #include<cstdlib> #include<cmath> #include<map> #include<stack> #include<set> #include<queue> #include<string> #include<vector> #define eps 1e-6 #define LL long long #define LD long double #define pi acos(-1.0) #define inf 1<<30 using namespace std; struct Node{ int idx,next; }a[1005]; int cnt,n,root,c[1005],num[1005],pre[1005],start[1005]; bool visit[1005]; int addedge(int u,int v){ a[cnt].idx=v; a[cnt].next=start[u]; return cnt++; } int find_root(){ double mmax=0; int k; for(int i=1;i<=n;i++) if(!visit[i]&&(double)c[i]/num[i]>mmax&&i!=root){ mmax=(double)c[i]/num[i]; k=i; } return k; } void Union(int k,int p){ num[p]+=num[k]; c[p]+=c[k]; for(int i=start[k];i;i=a[i].next) pre[a[i].idx]=p; } int slove(){ int ans=0; for(int i=1;i<n;i++){ int k=find_root(); visit[k]=true; int p=pre[k]; while(visit[p]) p=pre[p]; ans+=num[p]*c[k]; Union(k,p); } return ans+c[root]; } int main(){ while(scanf("%d%d",&n,&root)!=EOF&&n+root){ memset(start,0,sizeof(start)); memset(visit,false,sizeof(visit)); for(int i=1;i<=n;i++){ scanf("%d",&c[i]); num[i]=1; } cnt=1; for(int i=1;i<n;i++){ int u,v; scanf("%d%d",&u,&v); start[u]=addedge(u,v); pre[v]=u; } printf("%d\n",slove()); } return 0; }

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2017-01-18 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档