hdu 4738 Caocao's Bridges(2013杭州网络赛丶神坑)
就是求最小权值的桥。。不过有好几个坑。。。
1：原图不连通，ans=0.
2： m<=n^2 显然有重边，重边必然不是桥，处理重边直接add(u, v, INF).
3: 最小桥边权为0的时候，ans=1，至少要派一个人运炸弹。。。
#include<iostream>#include<algorithm>#include<vector>#include<string>#include<queue>#include<stack>#include<cstdio>#include<cstring>#include<cstdlib>#include<cmath>#include<fstream>#include<sstream>#include<map>#include<set>using namespace std;const int N = 1111;const int INF = 100000000;int n, m;int pre[N], low[N], dfs_clock;int bccno[N], vis[N], wi[N][N], g[N][N];struct Edge{ //flag = 1 ->bridge int from, to, w, flag;};vector<int> G[N];vector<Edge> edges;//add bidir edgevoid addedge(int u, int v, int w){ edges.push_back((Edge){u, v, w, 0}); edges.push_back((Edge){v, u, w, 0}); int nima = edges.size(); G[u].push_back(nima-2); G[v].push_back(nima-1);}int dfs(int u, int fa){ int lowu = pre[u] = ++dfs_clock; int sz = G[u].size(); for(int i=0; i<sz; i++) { int v = edges[G[u][i]].to; if(!pre[v]) { int lowv = dfs(v, u); lowu = min(lowu, lowv); if(lowv > pre[u]) edges[G[u][i]].flag = 1, edges[G[u][i]^1].flag = 1; } else if(pre[v] < pre[u] && v != fa) lowu = min(lowu, pre[v]); } return low[u] = lowu;}void dfs1(int u){ vis[u] = 1; int sz = G[u].size(); for(int i=0; i<sz; i++) { Edge e = edges[G[u][i]]; int v = e.to; if(!vis[v]) dfs1(v); }}int u, v, w;int main(){ while(scanf("%d%d", &n, &m), n+m) { for(int i=0; i<n+1; i++) G[i].clear(); edges.clear(); memset(g, 0, sizeof(g)); for(int i=0; i<m; i++) { scanf("%d%d%d", &u, &v, &w); u--; v--; g[u][v]++; //BIANSHU g[v][u]++; wi[u][v] = w; } //CHONG BIAN for(int i=0; i<n; i++) for(int j=0; j<n; j++) { if(g[i][j] == 1) addedge(i, j, wi[i][j]); else if(g[i][j] > 1) addedge(i, j, INF); } //BU LIANTONG memset(vis, 0, sizeof(vis)); dfs1(0); bool flag = 0; for(int i=0; i<n; i++) { if(!vis[i]) { flag = 1; break; } } if(flag) { puts("0"); continue; } //QIAO memset(pre, 0, sizeof(pre)); dfs_clock = 0; for(int i=0; i<n; i++) if(!pre[i]) dfs(i, -1); int ans = INF; int sz = edges.size(); for(int i=0; i<sz; i++) if(edges[i].flag == 1) ans = min(ans, edges[i].w); if(ans == INF) puts("-1"); else printf("%d\n", ans == 0 ? 1 : ans); //0 -> 1 } return 0;}