湘潭) H. Highway XTOJ 1267 【树的直径】"/>
2017ccpc全国邀请赛(湖南湘潭) H. Highway XTOJ 1267 【树的直径】
Highway | ||
Accepted : 168 | Submit : 576 | |
Time Limit : 4000 MS | Memory Limit : 65536 KB |
HighwayIn ICPCCamp there were n towns conveniently numbered with 1,2,…,n connected with (n−1) roads. The i -th road connecting towns ai and bi has length ci . It is guaranteed that any two cities reach each other using only roads. Bobo would like to build (n−1) highways so that any two towns reach each using only highways. Building a highway between towns x and y costs him δ(x,y) cents, where δ(x,y) is the length of the shortest path between towns x and y using roads. As Bobo is rich, he would like to find the most expensive way to build the (n−1) highways. InputThe input contains zero or more test cases and is terminated by end-of-file. For each test case: The first line contains an integer n . The i -th of the following (n−1) lines contains three integers ai , bi and ci .
OutputFor each test case, output an integer which denotes the result. Sample Input5 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 Sample Output19 15 SourceXTU OnlineJudge |
原题链接: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;
}
AC代码2:
参考博客:.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;
}
更多推荐
2017ccpc全国邀请赛(湖南湘潭) H. Highway XTOJ 1267 【树的直径】
发布评论