『Two 树的直径求解及其运用』 (2)

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 Format

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 解析

题目大意就是有一棵树， 在s结点放两个机器人， 这两个机器人会把树的每条边都走一遍, 但是最后机器人不要求回到出发点。问你两个机器人走的路总长之和的最小值是多少?

首先，我们假设只有一个机器人，那么答案是什么？
我们可以让机器人沿着从起点开始的某一条最远距离路径走，对于路径上的其他子树，机器人需要进入遍历，并返回，需要花费两倍的子树权值和，但由于机器人不需要回到起点，所以答案为\(2*\sum w_i-d\)，\(d\)为出发点所能到达的最远距离。同理，如果有两个机器人，那么我们就让他们分别向两条不同的路径走去，这样就正好对应了树的直径的\(BFS/DFS\)求法，机器人走的路径就成了树的直径，那么最终的答案就是\(2*\sum w_i-D\)，\(D\)为树的直径长度。

\(Code:\)

#include<cstdio> #include<iostream> #include<queue> #include<vector> #include<cstring> #define mset(name,val) memset(name,val,sizeof name) using namespace std; const int N=100000+50; int n,s,sum,vis[N],dis[N]; struct edge{int val,ver;}; vector < edge > Link[N]; inline void input(void) { scanf("%d%d",&n,&s); for(int i=1;i<n;i++) { int x,y,v; scanf("%d%d%d",&x,&y,&v); Link[x].push_back((edge){v,y}); Link[y].push_back((edge){v,x}); sum+=v*2; } } inline int Search(int start) { queue< int >q; mset(vis,0x00); mset(dis,0x00); vis[start]=1; q.push(start); while(!q.empty()) { int temp=q.front();q.pop(); for(int i=0;i<Link[temp].size();i++) { if(!vis[Link[temp][i].ver]) { vis[Link[temp][i].ver]=true; dis[Link[temp][i].ver]=dis[temp]+Link[temp][i].val; q.push(Link[temp][i].ver); } } } int res=0,Maxdis=0; for(int i=1;i<=n;i++) { if(dis[i]>Maxdis) { Maxdis=dis[i]; res=i; } } return res; } int main(void) { input(); int p=Search(s); printf("%d\n",sum-dis[Search(p)]); return 0; }