Caocao’s Bridges HDU - 4738
思路： 用targan算法找出图的强连通分量，并压缩成点，生成新图，便利新图找到最小边权即可。 注意：图本身可能就不连通，此时就不需要派人，答案为0。当最小边权为0，派一个人即可，答案为1。
code：
#include<iostream> #include<algorithm> #include<cmath> #include<stdlib.h> using namespace std; const int maxn = 1e3 + 5; const int dinif = 1e8; struct node{ int u, v, w, next; } g[maxn * maxn * 2]; int head[maxn]; int dfn[maxn], low[maxn], st[maxn], index[maxn], cnt, cot, opt, vcit; bool vis[maxn]; void add(int u, int v, int w){ g[vcit].next = head[u]; g[vcit].u = u; g[vcit].v = v; g[vcit].w = w; head[u] = vcit++; } void init(int n){ cnt = cot = opt = vcit = 0; for(int i = 1; i <= n; i++){ dfn[i] = low[i] = 0; vis[i] = false; index[i] = 0; head[i] = -1; } } void targan(int u, int fa){ dfn[u] = low[u] = ++cnt; vis[u] = true; st[cot++] = u; for(int i = head[u]; i != -1; i = g[i].next){ int v = g[i].v; if(!dfn[v]){ targan(v, i); low[u] = min(low[u], low[v]); } else if(vis[v] && i != (fa ^ 1)) low[u] = min(low[u], dfn[v]); } if(dfn[u] == low[u]){ int res; ++opt; do{ res = st[--cot]; index[res] = opt; vis[res] = false; } while(res != u); } } int main(){ int n, m, u, v, w; while(scanf("%d%d", &n, &m), n || m) { init(n); for(int i = 0; i < m; i++){ scanf("%d%d%d", &u, &v, &w); add(u, v, w); add(v, u, w); } int p = 0; for(int i = 1; i <= n; i++) if(!dfn[i]) targan(i, -1), p++; for(int i = 1; i <= n; i++) if(!index[i]) index[i] = ++opt; int mi = dinif; for(int i = 0; i < vcit; i++){ g[i].u = index[g[i].u]; g[i].v = index[g[i].v]; if(g[i].u != g[i].v) mi = min(mi, g[i].w); } if(mi == dinif) mi = -1; if(mi == 0) mi = 1; if(p > 1) mi = 0; printf("%d\n", mi); } return 0; }