POJ 1849 Two(树的直径--树形DP)（好题）

大致题意：在某个点派出两个点去遍历所有的边，花费为边的权值，求最少的花费

思路：这题关键好在这个模型和最长路模型之间的转换，可以转换得到，所有边遍历了两遍的总花费减去最长路的花费就是本题的答案，要思考，而且答案和派出时的起点无关

求最长路两遍dfs或bfs即可，从任意点bfs一遍找到最长路的一个终点，再从这个终点bfs找到起点

//1032K	79MS	C++	1455B	
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

const int N=1e5+100;
struct Edge
{
    int v,w;
    int next;
}es[N<<1];
int head[N];
int n,s;
bool vis[N];
int step[N];
int sum;
int bfs(int &st)
{
    int maxn=-1;
    step[st]=0;
    memset(vis,0,sizeof(vis));
    queue<int> que;
    if(!que.empty()) que.pop();
    que.push(st);
    vis[st]=true;
    while(!que.empty())
    {
        int cur=que.front();
        que.pop();
        for(int i=head[cur];~i;i=es[i].next)
        {
            int v=es[i].v;
            if(!vis[v])
            {
                que.push(v);
                step[v]=step[cur]+es[i].w;
                if(step[v]>maxn)
                {
                    maxn=step[v];
                    st=v;
                }
                vis[v]=true;
            }
        }
    }
    return maxn;
}
void ini()
{
    memset(head,-1,sizeof(head));
    sum=0;
}
int main()
{
    while(~scanf("%d%d",&n,&s))
    {
        ini();
        for(int i=1;i<n;i++)
        {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            sum+=w;
            es[i].v=v,es[i].w=w,es[i].next=head[u];
            head[u]=i;
            es[i+n].v=u,es[i+n].w=w,es[i+n].next=head[v];
            head[v]=i+n;
        }
        bfs(s);
        printf("%d\n",2*sum-bfs(s));

    }
    return 0;
}

POJ 1849 Two(树的直径--树形DP)（好题）

原文：http://blog.csdn.net/kalilili/article/details/44275169