“玲珑杯”ACM比赛 Round #18--最后你还是AK了(…
2018-06-17 22:12:35来源:未知 阅读 ()
INPUT
#define OPENSTACK #include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <vector> using namespace std; typedef long long LL; const int maxn=1e5+5; vector<pair<int,int> > v[maxn]; int c[maxn], cn[maxn], tmp, n; LL ans; int dfs(int p,int f) { int count=0; for(int i=0; i<v[p].size(); i++) { pair<int,int>pa=v[p][i]; if(pa.first==f) continue; int t=dfs(pa.first,p); cn[tmp]=min(t,n-t); ans+=(LL)cn[tmp]*(LL)pa.second; tmp++; count+=t; } return count+1; } int main() { #ifdef OPENSTACK long long size = 64 << 20; // 64MB char *p = (char*)malloc(size) + size; #if (defined _WIN64) or (defined __unix) __asm__("movq %0, %%rsp\n" :: "r"(p)); #else __asm__("movl %0, %%esp\n" :: "r"(p)); #endif #endif int T,k; cin>>T; while(T--) { for(int i=0;i<maxn;i++) v[i].clear(); scanf("%d%d",&n,&k); for(int i=1;i<n;i++) { int u1,u2,w; scanf("%d%d%d",&u1,&u2,&w); pair<int,int>pa1=make_pair(u1,w); pair<int,int>pa2=make_pair(u2,w); v[u1].push_back(pa2); v[u2].push_back(pa1); } for(int i=0;i<k;i++) scanf("%d",&c[i]); ans=0; tmp=0; int res=dfs(1,-1); //cout<<"点数-----"<<res<<endl; //cout<<" -----"<<ans<<endl; sort(cn,cn+tmp); sort(c,c+k); for(int i=tmp-1, j=k-1; j>=0; i--, j--) { ans+=(LL)c[j]*(LL)cn[i]; } printf("%lld\n",ans); } #ifdef OPENSTACK exit(0); #else return 0; #endif }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:Brackets
- 朋友(翻转树边权值比赛)——依然是思维 2020-04-12
- 凉肝的比赛 2020-01-18
- ACM | 算法 | 快速幂 2019-12-04
- 统计字符的个数,能够组成几个acmicpc 2019-10-16
- X Round 2(毒瘤比赛qwq) 2019-08-16
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash