題目鏈接:? HDU 4118 Holiday's Accommodation

分析: 可以知道每條邊要走的次數(shù)剛好的是這條邊兩端的點(diǎn)數(shù)的最小值的兩倍。

代碼:

?

    #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;

}




  

?

?

HDU 4118 樹(shù)形DP Holiday's Accommodation