题目大意：
有n个点，由m条边连接，第i条边的边权是wi。这些点和边构成了一个森林。你必须要新建若干条条权值为W天的边，使得原图恰好变成一棵树，并且让任意两个点间最长距离最短。求该通行时间
思路：
首先找出每棵树的直径和中心及其对应半径。
加边的过程一定是在这些中心之间加边。
考虑这些中心的连接方式。
选择一个中心，让其它中心都直接连上这个点肯定是最优的。
则答案要么是原树中的直径，要么是加边以后的新的直径。
新的直径分两种情况，一种是最大半径和次大半径直径直接用一条新边相连，另一种是次大边和第三大边用两条新边相连。
1 #include<cstdio> 2 #include<cctype> 3 #include<vector> 4 #include<cstring> 5 typedef long long int64; 6 inline int getint() { 7 register char ch; 8 while(!isdigit(ch=getchar())); 9 register int x=ch^'0'; 10 while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0'); 11 return x; 12 } 13 const int N=500000; 14 struct Edge { 15 int to,w; 16 }; 17 std::vector<Edge> e[N]; 18 inline void add_edge(const int &u,const int &v,const int &w) { 19 e[u].push_back((Edge){v,w}); 20 e[v].push_back((Edge){u,w}); 21 } 22 bool vis[N]; 23 int64 dis[N],ans; 24 int n,m,l,from[N],u,v; 25 void dfs1(const int &x,const int &par) { 26 vis[x]=true; 27 if(dis[x]>dis[u]) u=x; 28 for(unsigned i=0;i<e[x].size();i++) { 29 const int &y=e[x][i].to,&w=e[x][i].w; 30 if(y==par) continue; 31 dis[y]=dis[x]+w; 32 dfs1(y,x); 33 } 34 } 35 void dfs2(const int &x,const int &par) { 36 from[x]=par; 37 if(dis[x]>dis[v]) v=x; 38 for(unsigned i=0;i<e[x].size();i++) { 39 const int &y=e[x][i].to,&w=e[x][i].w; 40 if(y==par) continue; 41 dis[y]=dis[x]+w; 42 dfs2(y,x); 43 } 44 } 45 inline int64 find_center(const int &x) { 46 dis[u=x]=0; 47 dfs1(x,-1); 48 dis[v=u]=0; 49 dfs2(u,-1); 50 ans=std::max(ans,dis[v]); 51 int c=u; 52 for(register int i=v;~i;i=from[i]) { 53 if(std::max(dis[v]-dis[i],dis[i])<std::max(dis[v]-dis[c],dis[c])) c=i; 54 } 55 return std::max(dis[v]-dis[c],dis[c]); 56 } 57 inline void reset() { 58 for(register int i=0;i<n;i++) { 59 vis[i]=false; 60 e[i].clear(); 61 } 62 } 63 int main() { 64 while(~scanf("%d%d%d",&n,&m,&l)) { 65 for(register int i=0;i<m;i++) { 66 const int u=getint(),v=getint(),w=getint(); 67 add_edge(u,v,w); 68 } 69 int cnt=0; 70 int64 max1=0,max2=0,max3=0; 71 ans=0; 72 for(register int i=0;i<n;i++) { 73 if(vis[i]) continue; 74 cnt++; 75 int64 r=find_center(i); 76 if(r>max1) std::swap(r,max1); 77 if(r>max2) std::swap(r,max2); 78 if(r>max3) std::swap(r,max3); 79 } 80 if(cnt>=2) ans=std::max(ans,max1+max2+l); 81 if(cnt>2) ans=std::max(ans,max2+max3+l*2); 82 printf("%lld ",ans); 83 reset(); 84 } 85 return 0; 86 }