本文主要是介绍poj 1849 Two(树形dp求直径)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
树的直径：一棵树中两个点间的最长距离。
Description
The city consists of intersections and streets that connect them.
Heavy snow covered the city so the mayor Milan gave to the winter-service a list of streets that have to be cleaned of snow. These streets are chosen such that the number of streets is as small as possible but still every two intersections to be connected i.e. between every two intersections there will be exactly one path. The winter service consists of two snow plovers and two drivers, Mirko and Slavko, and their starting position is on one of the intersections.
The snow plover burns one liter of fuel per meter (even if it is driving through a street that has already been cleared of snow) and it has to clean all streets from the list in such order so the total fuel spent is minimal. When all the streets are cleared of snow, the snow plovers are parked on the last intersection they visited. Mirko and Slavko don’t have to finish their plowing on the same intersection.
Write a program that calculates the total amount of fuel that the snow plovers will spend.
Input
The first line of the input contains two integers: N and S, 1 <= N <= 100000, 1 <= S <= N. N is the total number of intersections; S is ordinal number of the snow plovers starting intersection. Intersections are marked with numbers 1...N.
Each of the next N-1 lines contains three integers: A, B and C, meaning that intersections A and B are directly connected by a street and that street's length is C meters, 1 <= C <= 1000.
Output
Write to the output the minimal amount of fuel needed to clean all streets.
Sample Input
5 2 1 2 1 2 3 2 3 4 2 4 5 1
Sample Output
6
题意两个人从同一个点开始遍历整个树经过每条边的价值为这个边的价值求遍历完这个树的时候的最小价值。暴力走的话肯定是2*(权值和)表示每个边都经过了两次，要想让这个价值尽可能的小那就找一条主路从这个主路开始走这条路只走一遍不回头然后其他的边这样就能最小价值。
#include <iostream>
#include<string>
#include <algorithm>
#include <string.h>
#include<cstdio>
using namespace std;
int ans=0,iv[1000050],v[1000050],ed[1000050],ne[10000000];
int f1[1000050],f2[1000050];
void add(int x,int y,int z){ans++;ne[ans]=iv[x];iv[x]=ans;v[ans]=y;ed[ans]=z;
}
int cnt=-1;
void dfs(int x,int fa){for(int i=iv[x];i;i=ne[i]){int y=v[i];if(y==fa)continue;dfs(y,x);if(f1[x]<f1[y]+ed[i]){f2[x]=f1[x];f1[x]=f1[y]+ed[i];}else if(f2[x]<f1[y]+ed[i])f2[x]=f1[y]+ed[i];cnt=max(cnt,f1[x]+f2[x]);}}
int main()
{int n,s;while(cin>>n>>s){memset(f1,0,sizeof(f1));memset(f2,0,sizeof(f2));cnt=ans=0;int cm=0;for(int i=1;i<n;i++){int x,y,z;cin>>x>>y>>z;add(x,y,z);add(y,x,z);cm+=2*z;}dfs(s,-1);cout<<cm-cnt<<endl;}
}
这篇关于poj 1849 Two(树形dp求直径)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
