http://codeforces.com/gym/100676/attachments
题目大意：
有n个城市，有m条路，每条路都有边长，如果某几个城市的路能组成一个环，那么在环中的这些城市就有传送门，能够瞬间抵达对方的城市（即距离为0），否则，就要走这条路，并且经过的路程为这条路的长度。
问，找一个城市作为这些城市的首都
要求：除了首都城市外，其他城市到首都的最大距离最短。
思路：
边双连通缩点以后就是一棵树，找树上的直径，首都一定是直径上的点。（orz，自己明明注意到了一定是直径上面的点，在之前的好多次的wa中却忘了是要找直径上的点了）
//看看会不会爆int!数组会不会少了一维！ //取物问题一定要小心先手胜利的条件 #include <bits/stdc++.h> using namespace std; #pragma comment(linker,"/STACK:102400000,102400000") #define LL long long #define ALL(a) a.begin(), a.end() #define pb push_back #define mk make_pair #define fi first #define se second #define haha printf("haha ") /* 思路： 双连通缩点，然后随便找一个点树dp， 树dp，距离最短的肯定就是直径上的某一个点 */ const int maxn = 1e5 + 5; const int maxm = 2e5 + 5; const LL inf = 1e17; vector<pair<int, LL> > G[maxn]; int n, m; /*****************/ int dfstime, bcccnt; bool iscut[maxn]; int bccnu[maxn], pre[maxn]; stack<int> s; vector<int> bcc[maxn]; int dfs(int u, int fa){ int lowu = pre[u] = ++dfstime; int len = G[u].size(); int child = 0; s.push(u); for (int i = 0; i < len; i++){ int v = G[u][i].fi; if (pre[v] == -1){ child++; int lowv = dfs(v, u); lowu = min(lowv, lowu); if (lowv > pre[u]){ iscut[u] = true; } } else if (pre[v] < pre[u] && v != fa){ lowu = min(lowu, pre[v]); } } if (lowu == pre[u]){ bcccnt++; while (true){///边双连通分量是不存在重点的 int v = s.top(); s.pop(); bccnu[v] = bcccnt; bcc[bcccnt].pb(v); if (v == u) break; } } if (fa == -1 && child == 1) iscut[u] = false; return lowu; } void get_connect(){ dfstime = bcccnt = 0; memset(iscut, false, sizeof(iscut)); memset(bccnu, 0, sizeof(bccnu)); memset(pre, -1, sizeof(pre)); dfs(1, -1); } vector<pair<int, LL> > new_edge[maxn]; void rebuild(){ ///O(n + m) for (int i = 1; i <= bcccnt; i++){ for (int j = 0; j < bcc[i].size(); j++){ int u = bcc[i][j]; for (int k = 0; k < G[u].size(); k++){ int v = G[u][k].fi; LL val = G[u][k].se; if (bccnu[u] != bccnu[v]){ new_edge[bccnu[u]].push_back(mk(bccnu[v], val)); } } } } /* printf("bcccnt = %d ", bcccnt); cout << "new_edge.output" << endl; for (int i = 1; i <= bcccnt; i++){ for (int j = 0; j < new_edge[i].size(); j++){ printf("u = %d v = %d val = %d ", i, new_edge[i][j].fi, new_edge[i][j].se); } cout << endl; } */ } int p; LL maxval; LL can[maxn]; void dfs1(int u, int fa, LL sum){ if (sum > maxval){ maxval = sum, p = u; } for (int i = 0; i < new_edge[u].size(); i++){ int v = new_edge[u][i].fi; LL tmp = new_edge[u][i].se; if (v == fa) continue; dfs1(v, u, sum + tmp); } } LL d1[maxn], d2[maxn]; ///d1从最底下到目前节点的距离 ///d2表示从根到目前节点的距离 void dfs2(int u, int fa, LL sum){ d2[u] = sum; for (int i = 0; i < new_edge[u].size(); i++){ int v = new_edge[u][i].fi; LL val = new_edge[u][i].se; if (v == fa) continue; dfs2(v, u, sum + val); d1[u] = max(d1[u], d1[v] + val); } } LL mini; vector<int> ansp; void dfs3(int u, int fa){ for (int i = 0; i < new_edge[u].size(); i++){ int v = new_edge[u][i].fi; LL val = new_edge[u][i].se; if (v == fa) continue; if (d1[u] - val == d1[v]){ dfs3(v, u); LL tmp = max(d1[u], d2[u]); if (mini > tmp){ ansp.clear(); mini = tmp; ansp.pb(u); } else if (mini == tmp){ ansp.pb(u); } } } } int main(){ int t; cin >> t; while (t--){ scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++){ G[i].clear(); bcc[i].clear(); new_edge[i].clear(); } for (int i = 1; i <= m; i++){ int u, v; LL val; scanf("%d%d%lld", &u, &v, &val); G[u].pb(mk(v, val)); G[v].pb(mk(u, val)); } get_connect(); rebuild(); p = 1, maxval = 0; dfs1(1, -1, 0); memset(d1, 0, sizeof(d1)); memset(d2, 0, sizeof(d2)); ansp.clear(); dfs2(p, -1, 0LL); mini = inf; dfs3(p, -1); int ans = n + 1; for (int i = 0; i < ansp.size(); i++){ int u = ansp[i]; for (int j = 0; j < bcc[u].size(); j++){ ans = min(ans, bcc[u][j]); } } if (ans == n + 1) {ans = 1, mini = 0;} printf("%d %lld ", ans, mini); } return 0; }