#include#include#includeusingnamespacestd;constintmaxn=100000+10;structnode{intto,dix,next;}tree[maxn<<1];inthead[ma" />

亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

HDU 4118 樹形DP Holiday's Accommodation

系統 2120 0

題目鏈接:? 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;

}




  


?


?

HDU 4118 樹形DP Holiday's Accommodation


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

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

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 亚洲欧美日韩精品香蕉 | 国产成人综合洲欧美在线 | 亚洲一区精品中文字幕 | 国产精品成人观看视频国产 | 日韩高清欧美精品亚洲 | 四虎影视精品 | 在线欧美v日韩v国产精品v | 国产精品亚洲欧美日韩久久 | 日韩在线2020专区 | 精品外国呦系列在线观看 | 国产免费一区二区三区在线观看 | 免费人成在线观看69式小视频 | 国产在线观看午夜不卡 | 一级毛片秋霞特色大片 | 国产精品日韩欧美在线第3页 | 色综合桃花网 | 欧美在线观看视频网站 | 伊人色综合久久天天网蜜月 | 夜夜艹日日干 | 日本一级黄色录像 | 精品国产免费第一区二区三区日韩 | 久久久精品免费国产四虎 | 2021久久精品国产99国产 | 久久免费视频观看 | 欧美激情伦妇在线观看 | 一级特黄aaa大片大全 | 特黄特黄一级高清免费大片 | 劲爆欧美色欧美 | 欧美一级毛片一免费 | 国产一级淫 | 欧美激情精品久久久久久久 | 天天久久狠狠色综合 | 偷偷鲁国内视频视频在线 | 亚洲日韩欧美一区二区在线 | 免费一区二区三区久久 | 亚洲精品日韩一区二区 | 国产在线视频你懂得 | 亚洲成人在线免费观看 | 四虎精品影院在线观看视频 | 四虎国产精品影库永久免费 | 草草影院国产第一页 |