https://vjudge.net/problem/Gym-100676H
题意：
给出一个n个城市，城市之间有距离为w的边，现在要选一个中心城市，使得该城市到其余城市的最大距离最短。如果有一些城市是强连通的，那么他们可以使用传送门瞬间到达。
思路：
因为强连通时可以瞬移，因为是无向图，所以计算边双连通分量然后重新建图，这样，也就不存在环了。
接下来，计算一下树的直径，因为中心城市肯定选在树的直径上，这样才有可能使最大的边最短。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<map>
using namespace std; const int maxn=1e5+;
const long long INF =1e15+;
typedef pair<long long,long long> pll; struct Edge
{
long long u,v,c;
}edge[maxn<<]; int n,m;
int pre[maxn],isbridge[maxn<<],bcc_cnt,dfs_clock;
long long d[maxn][];
vector<int> G[maxn];
vector<pll> tree[maxn]; int tarjan(int u,int fa)
{
int lowu=pre[u]=++dfs_clock;
for(int i=;i<G[u].size();i++)
{
int temp=G[u][i];
int v=edge[temp].v;
if(!pre[v])
{
int lowv=tarjan(v,u);
lowu=min(lowu,lowv);
if(lowv>pre[u])
{
isbridge[temp]=isbridge[temp^]=;
}
}
else if(v!=fa)
lowu=min(lowu,pre[v]);
}
return lowu;
} void dfs(int u)
{
pre[u]=bcc_cnt;
for(int i=;i<G[u].size();i++)
{
int temp=G[u][i];
if(isbridge[temp]) continue;
int v=edge[temp].v;
if(!pre[v]) dfs(v);
}
} void find_ebbc()
{
bcc_cnt=dfs_clock=;
memset(pre,,sizeof(pre));
memset(isbridge,,sizeof(isbridge)); for(int i=;i<=n;i++)
if(!pre[i]) tarjan(i,-); memset(pre,,sizeof(pre));
for(int i=;i<=n;i++) //计算边—双连通分量
if(!pre[i])
{
bcc_cnt++;
dfs(i);
}
} void rebuild()
{
for(int i=;i<=bcc_cnt;i++) tree[i].clear();
int tot=m<<|;
for(int i=;i<=tot;i+=)
{
if(isbridge[i])
{
int u=edge[i].v, v=edge[i].u;
tree[pre[u]].push_back(make_pair(pre[v],edge[i].c));
tree[pre[v]].push_back(make_pair(pre[u],edge[i].c));
}
}
} int bfs(int u,int flag)
{
for(int i=;i<=bcc_cnt;i++) d[i][flag]=-;
queue<int> Q;
Q.push(u);
d[u][flag]=;
long long max_d=;
int max_u=u;
while(!Q.empty())
{
u=Q.front(); Q.pop();
if(d[u][flag]>max_d) {max_d=d[u][flag];max_u=u;}
for(int i=;i<tree[u].size();i++)
{
int v=tree[u][i].first;
if(d[v][flag]==-)
{
Q.push(v);
d[v][flag]=d[u][flag]+tree[u][i].second;
}
}
}
return max_u;
} int main()
{
//freopen("D:\\input.txt","r",stdin);
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) G[i].clear();
for(int i=;i<=m;i++)
{
int u,v; long long w;
scanf("%d%d%lld",&u,&v,&w);
edge[i<<|].u=u; edge[i<<|].v=v; edge[i<<|].c=w;
edge[i<<].u=v; edge[i<<].v=u; edge[i<<].c=w;
G[u].push_back(i<<|);
G[v].push_back(i<<);
}
find_ebbc();
rebuild(); int p=bfs(,);
int q=bfs(p,); //计算出与一端点p的距离
long long length=d[q][];
int z=bfs(q,); long long ans=INF;
long long inx=n+;
for(int i=;i<=n;i++)
{
int cnt=pre[i];
if(d[cnt][]+d[cnt][]!=length) continue;
long long num=max(d[cnt][],d[cnt][]);
if(ans>num)
{
ans=num;
inx=i;
}
}
printf("%lld %lld\n",inx,ans);
}
return ;
}