2017ccpc全国邀请赛(湖南湘潭) H. Highway XTOJ 1267 【树的直径】

湘潭) H. Highway XTOJ 1267 【树的直径】"/>

2017ccpc全国邀请赛(湖南湘潭) H. Highway XTOJ 1267 【树的直径】

5
1 2 2
1 3 1
2 4 2
3 5 1
5
1 2 2
1 4 1
3 4 1
4 5 2

19
15

原题链接：http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1267

题意：n个城镇之间有n-1条道路相连，现在有个有钱人要来修n-1条高速公路，使得任意两个城镇之间都有唯一的高速公路，问你最多要花费多少钱。

对于样例1：

最远的两个点为4和5

对于1，从1修到4，花费4

对于2，从2修到5，花费4

对于3，从3修到4，花费5

对于4，从4修到5，花费6

对于5，从5修到4，花费6

从4到5和从5到4是一样的，算一次即可。

最终花费为4+4+5+6=19

对于此题，要用到树的直径，输的直径就是一棵树上最远的两个节点。

找到输的直径后，树上的点到直径上的两个端点(必为其中一个)的距离最远。

求直径的过程中就可以与处理处每个节点到端点的最短距离。

最后再遍历每个节点，找到最大的再相加就可以了。

AC代码1

参考博客：

设直径两个端点分别是 rt_1 和 rt_2 
代码的思路是先从1节点搜索到距离最远的直径上的节点rt_1，然后再从rt_1搜索找到距其最远的节点rt_2，同时更新每一个点到rt_1的距离，再从rt_2进行搜索更新每一个点到直径节点的距离，然后每个点到直径节点的最大距离进行累加。因直径考虑了两次，故减去一次直径就是最后的答案，三次搜索即可。

AC代码:

/*** 行有余力，则来刷题！* 博客链接:*
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=1e5+5;
typedef long long LL;
struct Node
{int v,next;LL w;
}edge[maxn<<1];
LL dis[maxn];
LL DIS;//树的直径
int head[maxn];
int cnt;bool vis[maxn];
int n;
int root1,root2;void addEdge(int u,int v,LL w)
{edge[cnt].v=v;edge[cnt].w=w;edge[cnt].next=head[u];head[u]=cnt++;
}
//求树的直径,
//u-起点,d-距离
void DFS1(int u, LL d)
{vis[u]=true;if(d>DIS){DIS=d;root1=u;}for(int i=head[u];~i;i=edge[i].next){int v=edge[i].v;LL w = edge[i].w;if(!vis[v]){DFS1(v,d+w);}}
}
void DFS2(int u,LL d ,bool type)
{vis[u]=true;dis[u]=max(dis[u],d);if(type&&d>DIS){root2=u;DIS=d;}for(int i=head[u];~i;i=edge[i].next){int v = edge[i].v;LL w = edge[i].w;if(!vis[v]){DFS2(v,d+w,type);}}
}
void solve()
{root1=root2=0;memset(vis,false,sizeof(vis));DIS=0;DFS1(1,0);memset(dis,0,sizeof(dis));memset(vis,false,sizeof(vis));DIS=0;DFS2(root1,0,true);memset(vis,false,sizeof(vis));DFS2(root2,0,false);LL ans=0;dis[root1]=0;//cout<<root1<<","<<root2<<endl;for(int i=1;i<=n;i++){ans += dis[i];}cout<<ans<<endl;
}
int main()
{//freopen("C:\\Documents and Settings\\Administrator\\桌面\\data.txt","r",stdin);while(cin>>n){memset(head,-1,sizeof(head));cnt=0;int u,v;LL w;for(int i=1;i<n;i++){//cin>>u>>v>>w;scanf("%d%d%I64d",&u,&v,&w);addEdge(u,v,w);addEdge(v,u,w);}solve();}return 0;
}

参考博客:.html

只用了一个DFS,但是每次搜索的时候都要把根节点传递进去,我用了vis来标记,搜索减少了一个参数.

/*** 行有余力，则来刷题！* 博客链接:*
*/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=1e5+5;
typedef long long LL;
struct Edge
{int v,next;LL w;Edge() {}Edge(int v,int next,LL w):v(v),next(next),w(w) {}
} edge[maxn<<1];LL dis[2][maxn];
int n;
int cnt;
int head[maxn];
bool vis[maxn];
int p;//记录直径端点
LL D;//树的直径
void addEdge(int u,int v,LL w)
{edge[cnt]=Edge(v,head[u],w);head[u]=cnt++;
}void DFS(int u,int k)
{vis[u]=true;if(dis[k][u] > D){p = u;D = dis[k][u];}for(int i = head[u]; ~i; i = edge[i].next){int v = edge[i].v;//注意此处标记的是v而不是i !!!!!if(!vis[v]){vis[v]=true;dis[k][v] = edge[i].w + dis[k][u];DFS(v, k);}}
}
int main()
{//freopen("C:\\Documents and Settings\\Administrator\\桌面\\data.txt","r",stdin);while(cin>>n){memset(head,-1,sizeof(head));cnt=0;int u,v;LL w;for(int i=1; i<n; i++){scanf("%d%d%I64d",&u,&v,&w);addEdge(u,v,w);addEdge(v,u,w);}memset(vis,false,sizeof(vis));memset(dis,0,sizeof(dis));//从1开始,找树的直径的一个端点r1dis[0][1]=0;D=0;DFS(1,0);int r1=p;//r1为一个端点//从r1开始,找树的直径的另一个端点r2//并记录r1到每个点的最短距离dis[0][]memset(vis,false,sizeof(vis));dis[0][r1]=0;D=0;DFS(r1,0);int r2=p;//求r2到每个点的最短距离dis[1][]memset(vis,false,sizeof(vis));dis[1][r2]=0;DFS(r2,1);//cout<<r1<<","<<r2<<endl;//遍历每个节点,求出到直径端点的最大值LL ans=0;for(int i=1; i<=n; i++){ans+=max(dis[0][i],dis[1][i]);}//树的直径加了两次cout<<ans-D<<endl;//cout<<ans-dis[1][r1]<<endl;//cout<<ans-dis[0][r2]<<endl;}return 0;
}