POJ 1849 Two(遍历树)
题意:
有一颗n个结点的带权的无向树, 在s结点放两个机器人, 这两个机器人会把树的每条边都走一遍, 可是最后机器人不要求回到出发点. 问你两个机器人走的路总长之和的最小值是多少?
分析:
首先本题仅仅要求出树的直径, 然后用树的总长sum*2-树的直径就是所求结果. 以下一步步来说明为什么是这种.
1.如果仅仅有1个机器人遍历树,且要求回到原点, 它最少须要走多少路?
答: 它须要走树总长sum的两倍, 即每条树边它都要走两次才行. 这个结论画个图就明确了, 对于每条边, 机器人要走过该边, 之后还要从该边回去(不回来就不能回到出发点了). 所以自然是sum*2.
2.如果1问中的机器人遍历树,可是不要求它回到原点, 那么它最少须要走多少路?
答: 最少须要走sum-[从出发点能走到最远的点的距离]. 在行走的过程中每一个分叉, 它走过去,又走回来就可以. 能够反证得出.
3.如果有两个机器人从s出发,遍历整个树且终于回到出发点. 它们行走的最短距离是?
答: . 每一个机器人都必须回到原点, 那么必定每条边至少要被走两次.
4.如果有两个机器人从s出发,遍历整个树且它们不须要回到出发点. 它们行走的最短距离是?
答: 树总长的两倍-树的直径. 机器人出去不回来，则所走路径中有一条简单路径是能够仅仅走一遍的，派出了两个点去遍历，也就是说有两条简单路径是能够直走一边的，我们要使这两条简单路径的总和尽可能的长，就转换为了树的最长路径问题了.
注意:上面第4种情况, 两个机器人从哪点出发都是没有不论什么差别的. 由于假设它们出发点不在树的直径上, 那么它们一定能够一起移动到树直径上的某个点上,然后分别朝树直径的两个方向走, 而且遍历它们走的树直径的全部分叉路两次.
AC代码:
#include#include #include #include using namespace std;const int maxn=100000+5;//边结构struct Edge{ Edge(){} Edge(int to,int cost,int next):to(to),cost(cost),next(next){} int to; int cost; int next;}edges[maxn];int cnt=0;//总边数int head[maxn];//加入两条有向边void AddEdge(int u,int v,int cost){ edges[cnt]=Edge(v,cost,head[u]); head[u]=cnt++; edges[cnt]=Edge(u,cost,head[v]); head[v]=cnt++;}int dist[maxn];//返回从s能到达的最长点编号int BFS(int s){ int max_dist=0; int id=s; queue Q; memset(dist,-1,sizeof(dist)); dist[s]=0; Q.push(s); while(!Q.empty()) { int u=Q.front(); Q.pop(); if(dist[u]>max_dist) max_dist=dist[id=u]; for(int i=head[u]; i!=-1; i=edges[i].next) { Edge &e=edges[i]; if(dist[e.to]==-1) { dist[e.to]=dist[u]+e.cost; Q.push(e.to); } } } return id;}int main(){ int n,s; while(scanf("%d%d",&n,&s)==2) { int sum=0;//树的总长 memset(head,-1,sizeof(head)); cnt=0; for(int i=1;i<=n-1;i++) { int u,v,cost; scanf("%d%d%d",&u,&v,&cost); sum+=cost; AddEdge(u,v,cost); } printf("%d\n",sum*2-dist[BFS(BFS(s))]); } return 0;}