【描述】 L因为业务繁忙，经常会到处出差。因为他是航空公司的优质客户，于是某个航空 公司给了他一个优惠券。 他可以利用这个优惠券在任何一个国家内的任意城市间免费旅行，当他的路线跨国 才会产生费用。 L有一个航空公司的价格表与航线。而且每个城市出发都能到所有的城 市， 2 个城市间可能有不止一个航班，一个国家内的 2个城市间一定有不同的路线，但是 不同国家的城市间只有一条路线。 L想知道从每个城市出发到产生费用最多的城市，不过 你不能重复在一个航班上飞来飞去产生费用，不行沿最少的费用路线飞行。 【输入】 第一行，两个整数 N,M，表示 N 个城市， M 条航线。 接下来 M 行，每行三个整数 a,b,c，表示城市 a,b 之间有一条费用为 c 的航 线。 【输出】 共 N 行，第 i 行为从城市 i 出发到达每个城市额外费用的最大值。 【Sample Input】 6 6 1 4 2 1 2 6 2 5 3 2 3 7 6 3 4 3 1 8 【Sample Output】 4 4 4 6 7 7 【解释】 有四个国家，包含的城市分别为 {1,2,3},{4},{5},{6}。 从城市 1 出发到达城市 6，乘坐(1,3)(3,6)两个航班费用最大， (1,3)在国内为免费航 班， (3,6)的费用为 4，所以从 1 出发的最大费用为 4。 【数据规模】 对于 40%的数据 1<=N<=1000,1<=M<=1000 对于 100%的数据 1<=N<=20000,1<=M<=200000
首先，在一个国家的城市肯定属于同一个边双联通分量，因此我们对于无向图跑一遍tarjan，然后缩点
现在整个图变成了一颗树，相当于就是让我们求一个点在树上的最长距离是多少
先求出树的直径，设端点为A,B，那么每个点的最长距离就是max(dis[A],dis[B])
可以用反证法来证明，假如最长距离是到点C，那么树的直径就会变化了
代码很好实现，只需两发dfs即可
#include<bits/stdc++.h> #define N 20005 #define M 200005 using namespace std; struct Edge { int to,next,val; }edge[2*M]; int first[N],tot; int n,m; inline void addedge(int x,int y,int z) { tot++; edge[tot].to=y; edge[tot].next=first[x]; edge[tot].val=z; first[x]=tot; } stack <int> sta; bool insta[N]; int dfn[N],low[N],sign,num,belong[N]; void dfs(int now,int fa) { dfn[now]=low[now]=++sign; insta[now]=true; sta.push(now); for(int u=first[now];u;u=edge[u].next) { int vis=edge[u].to; if(vis==fa) continue; if(!dfn[vis]){ dfs(vis,now); low[now]=min(low[now],low[vis]); } else if(insta[vis]) low[now]=min(low[now],dfn[vis]); } if(dfn[now]==low[now]) { int top; num++; do { top=sta.top(); insta[top]=false; belong[top]=num; sta.pop(); } while(top!=now); } } struct SCC { int to,next,val; }scc[2*M]; int head[N]; inline void addscc(int x,int y,int z) { tot++; scc[tot].to=y; scc[tot].next=head[x]; scc[tot].val=z; head[x]=tot; } int maxdis,disA[N],disB[N],point; void dfs1(int now,int fa) { for(int u=head[now];u;u=scc[u].next) { int vis=scc[u].to; if(vis==fa) continue; disA[vis]=disA[now]+scc[u].val; if(disA[vis]>maxdis) { maxdis=disA[vis]; point=vis; } dfs1(vis,now); } } void dfs2(int now,int fa) { for(int u=head[now];u;u=scc[u].next) { int vis=scc[u].to; if(vis==fa) continue; disB[vis]=disB[now]+scc[u].val; dfs2(vis,now); } } int main() { ios::sync_with_stdio(false); cin.tie(NULL),cout.tie(NULL); cin>>n>>m; for(int i=1;i<=m;i++) { int a,b,c; cin>>a>>b>>c; addedge(a,b,c); addedge(b,a,c); } for(int i=1;i<=n;i++) if(!dfn[i]) dfs(i,0); tot=0; for(int i=1;i<=n;i++) { for(int u=first[i];u;u=edge[u].next) { int vis=edge[u].to; if(belong[i]!=belong[vis]) addscc(belong[i],belong[vis],edge[u].val); } } dfs1(1,-1); memset(disA,0,sizeof(disA)),maxdis=0; dfs1(point,-1); dfs2(point,-1); for(int i=1;i<=n;i++) cout<<max(disA[belong[i]],disB[belong[i]])<<'\n'; return 0; }