题目链接：http://codeforces.com/gym/100676/attachments
题意：
有 n 个点，m 条边，图中，边强连通分量之间可以直达，即距离为 0 ，找一个点当做首都，其他点到首都的最大距离最小。
参考：http://www.cnblogs.com/ost-xg/p/6395100.html
仔细研究了大佬的思路，很牛逼，但是也有一点细节遗漏了，但是还是能AC，interesting；
分析：
边双连通：条件比点双连通松一点，体现在程序中，就是存在一个子节点能到达的最早祖先在父节点之后（没有等于）；这样桥就找到了，然后再去找边双连通分量——dfs，从一个点出发，是桥就不是同一个边双连通分量；
这样就把题目中的边双连通分量找出来了；
然后缩点重新建图ed的边集！！！（遍历每一条边，是桥就加上来，大佬的这里多加了哦）
此时，怎么选首都呢？
其实，现在图已经是一棵树了，遍历每一个点跑最短路是傻逼行为；
先找到树的直径，首都一定在这条直径上，枚举直径上的点，最远的，不过是直径上的两个部分；
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 const int maxn = 100005; 6 const long long inf = 1e15 + 5; 7 8 struct Edge 9 { 10 long long u, v, c; 11 } e[maxn<<2]; 12 struct Ed 13 { 14 long long v, c; 15 }; 16 17 int n, m, low[maxn], pre[maxn], tim, ebcc_cnt, du[maxn]; 18 long long k, len, dis[maxn][2]; 19 vector<int> G[maxn]; 20 vector<Ed> ed[maxn]; 21 int isbri[maxn<<4]; 22 bool vis[maxn]; 23 24 void init() 25 { 26 ebcc_cnt = tim = 0; 27 for (int i = 1; i <= n; i++) G[i].clear(); 28 memset(isbri, 0, sizeof(isbri)); 29 memset(pre, 0, sizeof(pre)); 30 memset(du, 0, sizeof(du)); 31 } 32 33 void tarjan(int u, int fa) 34 { 35 low[u] = pre[u] = ++tim; 36 for (int i = 0; i < G[u].size(); i++) 37 { 38 int tmp = G[u][i]; 39 int v = e[tmp].v; 40 if (!pre[v]) 41 { 42 tarjan(v, u); 43 low[u] = min(low[u], low[v]); 44 if (low[v] > pre[u]) 45 isbri[tmp] = isbri[tmp^1] = true; //标记为桥 46 } 47 else if (fa != v) 48 low[u] = min(low[u], pre[v]); 49 } 50 } 51 52 void dfs(int u) 53 { 54 pre[u] = ebcc_cnt; 55 for (int i = 0; i < G[u].size(); i++) 56 { 57 int tmp = G[u][i]; 58 if (isbri[tmp]) continue; 59 int v = e[tmp].v; 60 if (pre[v]) continue; 61 dfs(v); 62 } 63 } 64 65 void find_ebcc() 66 { 67 tarjan(1, -1); 68 memset(pre, 0, sizeof(pre)); 69 for (int i = 1; i <= n; i++) 70 { 71 if (!pre[i]) 72 { 73 ebcc_cnt++; 74 dfs(i); 75 } 76 } 77 } 78 79 void BFS(int s, int ca) 80 { 81 memset(vis, 0, sizeof(vis)); 82 queue<Ed> q; 83 q.push((Ed) 84 { 85 s, 0 86 }); 87 vis[s] = 1; 88 while (q.size()) 89 { 90 Ed tmp = q.front(); 91 q.pop(); 92 dis[tmp.v][ca] = tmp.c; 93 for (int i = 0; i < ed[tmp.v].size(); i++) 94 { 95 Ed xx = ed[tmp.v][i]; 96 if (!vis[xx.v]) 97 { 98 vis[xx.v] = 1; 99 q.push((Ed) 100 { 101 xx.v, xx.c + tmp.c 102 }); 103 } 104 } 105 } 106 } 107 108 void dfs_len(int x, int fa, long long dep) 109 { 110 if (dep > len) 111 { 112 k = x; 113 len = dep; 114 } 115 for (int i = 0; i < ed[x].size(); i++) 116 { 117 Ed tmp = ed[x][i]; 118 if (tmp.v == fa) continue; 119 dfs_len(tmp.v, x, dep + tmp.c); 120 } 121 } 122 123 int main() 124 { 125 int t = 1; 126 cin >> t; 127 128 while (t--) 129 { 130 cin >> n >> m; 131 init(); 132 for (int i = 1; i <= m; i++) 133 { 134 int u, v, c; 135 scanf("%d%d%d", &u, &v, &c); 136 e[i<<1|1].u = u, e[i<<1|1].v = v, e[i<<1|1].c = c; 137 e[i<<1].u = v, e[i<<1].v = u, e[i<<1].c = c; 138 G[u].push_back(i<<1|1); 139 G[v].push_back(i<<1); 140 } 141 find_ebcc(); 142 int tot = m<<1|1; 143 for (int i = 1; i <= ebcc_cnt; i++) ed[i].clear(); 144 for (int i = 3; i <= tot; i += 2) 145 { 146 if (isbri[i]) 147 { 148 int u = e[i].v, v = e[i].u; 149 ed[pre[u]].push_back((Ed) 150 { 151 pre[v], e[i].c 152 }); 153 ed[pre[v]].push_back((Ed) 154 { 155 pre[u], e[i].c 156 }); 157 } 158 } 159 len = -1; 160 dfs_len(1, -1, 0); 161 int st = k; 162 len = -1; 163 dfs_len(st, -1, 0); 164 BFS(st, 0); 165 BFS(k, 1); 166 long long inx = n + 1, dd = inf; 167 for (int i = 1; i <= n; i++) 168 { 169 int pr = pre[i]; 170 if (dis[pr][0] + dis[pr][1] != len) continue; 171 long long tmp = max(dis[pr][0], dis[pr][1]); 172 if (tmp < dd) 173 { 174 inx = i; 175 dd = tmp; 176 } 177 } 178 printf("%lld %lld ",inx,dd); 179 } 180 return 0; 181 }