洛谷比赛 U5442 买(最长链)

U5442 买

题目提供者bqsgwys

标签 树形结构树的遍历洛谷原创

题目背景

小E是个可爱的电路编码员。

题目描述

一天小E又要准备做电路了，他准备了一个电路板，上面有很多个电路元器件要安装，于是他跑到了村口某电子城去买。小E详细查看了某电子城的地图，发现自己要去地下一层，共有N个摊铺，任意两个摊铺之间由道路直接或间接相连，一共N-1条道路，道路是双向的。小E一开始处于1号摊铺的位置，由于电子城里很挤，他想走的尽量少。

输入输出格式

输入格式：

第一行一个整数N，代表摊铺的数目。

接下来N-1行，每行三个整数s, t, w，表示有一条从s号铺到t号铺的双向道路，长度为w。s和t的编号从1开始。

输出格式：

一个整数，代表对于每组数据能够访问每个摊铺至少一次的方案的最小行动长度。

输入输出样例

输入样例#1：

3

1 2 3

1 3 3

输出样例#1：

9

说明

1≤N≤50000，1≤w≤1000

/*

这题可以证明是求边权之和*2-最长链.

bfs从根的左树和右树分别跑最长链取大.

*/

#include<iostream>

#include<cstring>

#include<cstdio>

#include<queue>

#define MAXN 50001

using namespace std;

int head[MAXN],n,m,cut,ans,maxans,ans1,ans2,maxt,dis[MAXN],tot,fa[MAXN],tot1,tot2;

struct data{int v,next,x;}e[MAXN*2];

bool b[MAXN];

int read1()

{

    int x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();

    return x*f;

}

void add(int u,int v,int z)

{

    e[++cut].v=v;

    e[cut].next=head[u];

    e[cut].x=z;

    head[u]=cut;

}

void dfs(int u,int f)

{

    fa[u]=f;

    for(int i=head[u];i;i=e[i].next)

    {

        int v=e[i].v;

        if(f!=v&&!fa[v])

        {

            if(u==1)

            {

                if(!tot1) tot1=v,ans1=e[i].x;

                else tot2=v,ans2=e[i].x;

            }

            tot+=e[i].x;

            dfs(v,u);

        }

    }

}

void spfa(int s)

{

    int u,v;

    memset(dis,-1,sizeof dis);

    memset(b,0,sizeof b);

    queue<int>q;q.push(s);dis[s]=0;

    while(!q.empty())

    {

        u=q.front();q.pop();b[u]=false;

        for(int i=head[u];i;i=e[i].next)

        {

            v=e[i].v;

            if(v==1) continue;

            if(dis[v]==-1)

            {

                dis[v]=dis[u]+e[i].x;

                if(dis[v]>ans)

                {

                    ans=dis[v];

                    maxt=v;

                }

                if(!b[v]) b[v]=true,q.push(v);

            }

        }

    }

}

int main()

{

    int x,y,z;

    n=read1();

    for(int i=1;i<=n-1;i++)

    {

        x=read1(),y=read1(),z=read1();

        add(x,y,z);add(y,x,z);

    }

    dfs(1,1);

    spfa(tot1);

    ans+=ans1;

    maxans=max(maxans,ans);

    ans=0;spfa(tot2);ans+=ans2;

    maxans=max(maxans,ans);

    printf("%d",2*tot-maxans);

    return 0;

}

巴特西

洛谷比赛 U5442 买(最长链)

最新文章

热门文章