HDU 4738 双连通模版题
九野的博客，转载请注明出处：http://blog.csdn.net/acmmmm/article/details/11711577
题意：给定n个点，m条无向边
下面m行表示u , v ,边权值
求所有桥中最小的桥的权值，如不存在输出-1
若图一开始就不连通或最小权值为0则输出1
双连通求桥裸题
附赠一大波测试数据：
#include <string.h> #include <cstdio>#include <vector> #define N 1010#define inf 10000000using namespace std;inline int Min(int a,int b){return a>b?b:a;}vector<int>G[N];int dis[N][N],bian[N][N];int n,m,f[N];int find(int x){return x==f[x]?x:f[x]=find(f[x]);}void Union(int u,int v){ int fa=find(u),fb=find(v); f[fa]=fb;}struct node{ int u,v,d;}edge[N];//割边不会超过n条int edgenum;void PUT(int u,int v,int d){ node E={u,v,d}; edge[edgenum++]=E;}int pre[N],low[N],dfs_clock;bool su;int dfs(int u,int fa){//是连通图,dfs(u, )目的是寻找u的后代所能连回的（最早的祖先）的pre值 if(su)return 0;int lowu=pre[u]= ++ dfs_clock; int child=0; for(int i=0;i<G[u].size();i++){ int v=G[u][i]; if(!pre[v]){ child++; int lowv=dfs(v,u); lowu = Min(lowu, lowv);if(lowv > pre[u]&&bian[u][v]==1){PUT(u,v,dis[u][v]);if(dis[u][v]<=1)return 0;} } else if(pre[v] < pre[u] && v!=fa) lowu = Min(lowu, pre[v]); } return low[u]=lowu;}void findcut(){ memset(pre,0,sizeof(pre)); dfs_clock=0; dfs(1,-1);//dfs(树根，树根的父亲是-1) }int main(){ int i,u,v,d; while(scanf("%d %d",&n,&m),n) { memset(bian,0,sizeof(bian)); for(i=1;i<=n;i++) { G[i].clear(); f[i]=i; for(int j=1;j<=n;j++) dis[i][j]=inf; } while(m--) { scanf("%d %d %d",&u,&v,&d);if(dis[u][v]==inf){ G[u].push_back(v); G[v].push_back(u); Union(u,v);} dis[u][v]=dis[v][u]=Min(dis[u][v],d); bian[u][v]++; bian[v][u]++; } bool fa=false;find(1); for(i=1;i<=n;i++)if(find(i)!=f[1]){fa=true;break;} if(fa){printf("0\n");continue;}su=false;edgenum=0; findcut(); if(edgenum) { int ans=inf; for(i=0;i<edgenum;i++)ans=Min(ans,edge[i].d); if(ans==inf)ans=-1; else if(ans==0)ans=1; printf("%d\n",ans); } else printf("-1\n"); } return 0;}/* 3 3 1 2 7 2 3 4 3 1 4 3 2 1 2 7 2 3 4 3 4 1 2 7 2 1 7 2 3 4 3 2 4 4 3 1 2 1 1 2 3 3 4 4 4 4 1 2 1 1 2 3 3 4 4 2 4 6 4 5 1 2 1 1 2 3 3 4 4 2 4 6 1 3 0 4 5 4 3 0 3 4 4 2 4 6 2 3 0 1 3 0 2 1 1 2 0 4 2 1 2 3 1 3 5 4 5 1 2 3 2 3 4 1 3 5 4 3 7 4 3 6 4 4 1 2 3 2 3 4 1 3 5 4 3 6 4 4 1 2 4 1 3 5 4 3 6 3 4 7 6 7 1 2 1 1 3 2 2 3 3 3 4 4 4 6 5 4 5 6 5 6 7 5 6 1 2 3 1 3 4 2 3 5 3 4 7 3 5 8 5 4 9 8 9 1 8 1 5 1 2 1 7 3 1 4 4 1 2 5 4 3 6 3 2 7 5 6 8 6 7 9 6 6 1 4 1 1 2 4 2 5 4 5 6 4 3 6 4 4 3 2 6 5 1 2 4 2 5 4 5 6 4 3 6 4 4 3 2 8 10 1 8 1 5 1 2 1 7 3 1 4 4 1 2 5 4 3 6 3 2 7 5 6 8 6 7 9 8 1 2 3 3 1 2 7 1 3 1 1 3 4 0 0 */
代码2：
#include<iostream>#include<stdio.h>#include<string>#include<string.h>#include<algorithm>#include<map>#include<list>#include<set>#include<vector>#include<queue>#include<iomanip>#include<math.h>#define N 1010#define M 1000100#define inf 1000000000using namespace std;int n,m;//n个点 m条边struct node{int to,val,nex;bool cut;}edge[2*M];int head[N],edgenum;//在一开始就要 memset(head,-1,sizeof(head)); edgenum=0;int low[N],dfn[N],tarjin_time;void add(int u,int v,int w){node E={v,w,head[u],0};edge[edgenum]=E;head[u]=edgenum++;}void tarjin(int u,int pre){low[u]=dfn[u]= ++tarjin_time;int flag=1;//去重边，有重边那么(u,v)一定不是桥for(int i=head[u];i!=-1;i=edge[i].nex){int v=edge[i].to;if(flag&&v==pre){flag=0;continue;}if(!dfn[v]){tarjin(v,u);if(low[u]>low[v])low[u]=low[v];if(low[v]>dfn[u])//是桥edge[i].cut=edge[i^1].cut=true;}else if(low[u]>dfn[v])low[u]=dfn[v];}}bool liantong;//是否连通void find_edgecut(){memset(dfn,0,sizeof(dfn));tarjin_time=0;tarjin(1,1);liantong=true;for(int i=1;i<=n;i++)if(!dfn[i]){liantong=false;return;}}int main(){int i,j,k;while(~scanf("%d%d",&n,&m),n){memset(head,-1,sizeof(head));edgenum=0;while(m--){scanf("%d%d%d",&i,&j,&k);add(i,j,k);add(j,i,k);}find_edgecut();int ans=inf;if(liantong==false){puts("0");continue;}for(int i=0;i<edgenum;i++)if(edge[i].cut){if(edge[i].val<ans)ans=edge[i].val;}if(ans==inf)ans=-1;if(ans==0)ans=1;printf("%d\n",ans);}return 0;}