題目鏈接:?
HDU 4118 Holiday's Accommodation
分析: 可以知道每條邊要走的次數剛好的是這條邊兩端的點數的最小值的兩倍。
代碼:
?
#include<iostream> #include<cstdio> #include<cstring> #include<stack> using namespace std; const int maxn=100000+10; struct node{ int to, dix, next; }tree[maxn<<1]; int head[maxn],g[maxn],ptr; bool vis[maxn]; void Init(){ ptr=1; memset(vis,false,sizeof(vis)); memset(head,-1,sizeof(head)); } void AddEdge(int a,int b,int c){ tree[ptr].to=b; tree[ptr].dix=c; tree[ptr].next=head[a]; head[a]=ptr++; } void DFS(){ vis[1]=true; stack<int>M; M.push(1); int rt=head[1]; while(true){ if(rt==-1){ int a=M.top(); M.pop(); if(M.empty()) break; g[M.top()]+=g[a]; } rt=head[M.top()]; while(rt!=-1){ if(!vis[tree[rt].to]){ vis[tree[rt].to]=true; M.push(tree[rt].to); break; } rt=tree[rt].next; } } } int main(){ int T,cas=1; scanf("%d",&T); while(T--){ Init(); int n; scanf("%d",&n); for(int i=1;i<n;++i){ int a,b,c; scanf("%d%d%d",&a,&b,&c); AddEdge(a,b,c); AddEdge(b,a,c); g[i]=1; } g[n]=1; DFS(); __int64 ans=0; for(int i=1;i<ptr;i+=2){ int m=min(g[tree[i].to],g[tree[i+1].to]); ans+=2*min(n-m,m)*(__int64)tree[i].dix; } printf("Case #%d: %I64d\n",cas++,ans); } return 0; }
?
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
