题意：
给出 n 个点 m 条边的无向图，输出权值最小的桥
题解：
桥模板题
如果无向图本身就已经是不连通的了，直接输出 0 即可 （用并查集判断一下）
因为存在权值为 0 的情况，因此如果求出来的最小权值桥的权值为 0 时，根据题意，输出 1。
注意处理重边
代码：
#include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> #include<vector> #include <map> using namespace std; typedef long long ll; const int inf=0x3f3f3f3f; const int maxn = 1e4+5;//点数 const int maxm = 2e6+5;//边数，因为是无向图，所以这个值要*2 struct Edge { int to,next; int w; bool cut;//是否是桥标记 } edge[maxm]; int head[maxn],tot; int low[maxn],dfn[maxn],Stack[maxn],belong[maxn];//belong数组的值是1~scc int Index,top; int scc;//边双连通块数/强连通分量的个数 bool Instack[maxn]; int bridge;//桥的数目 int cut[maxn]; int num[maxn]; void addedge(int u,int v,int w) { edge[tot].to = v; edge[tot].next = head[u]; edge[tot].cut=false; edge[tot].w=w; head[u] = tot++; } void Tarjan(int u,int pre) { int v; low[u] = dfn[u] = ++Index; Stack[top++] = u; Instack[u] = true; int son=0; int flag=0; for(int i = head[u]; i != -1; i = edge[i].next) { v = edge[i].to; if(v == pre && !flag) { flag++; continue; } if( !dfn[v] ) { son++; Tarjan(v,u); if( low[u] > low[v] )low[u] = low[v]; if(low[v] > dfn[u]) { bridge++; edge[i].cut = true; edge[i^1].cut = true; } if(u == pre && son > 1)cut[u] = true; if(u != pre && low[v] >= dfn[u])cut[u] = true; } else if( Instack[v] && low[u] > dfn[v] ) low[u] = dfn[v]; } if(low[u] == dfn[u]) { scc++; do { v = Stack[--top]; Instack[v] = false; belong[v] = scc; num[scc]++; } while( v!=u ); } } void init() { tot = 0; memset(head,-1,sizeof(head)); } int solve(int n) { memset(dfn,0,sizeof(dfn)); memset(Instack,false,sizeof(Instack)); memset(cut,0,sizeof cut); memset(num,0,sizeof num); Index = top = scc = 0; bridge = 0; for(int i = 1; i <= n; i++) if(!dfn[i]) Tarjan(i,i); int res=inf; for(int u=1;u<=n;u++) { for(int i=head[u];~i;i=edge[i].next) if(edge[i].cut)res=min(res,edge[i].w); } if(res==inf)return -1; if(res==0)return 1; return res; } int pre[maxn]; int Find(int x) { return x==pre[x]?x:pre[x]=Find(pre[x]); } int join(int x,int y) { int fx=Find(x); int fy=Find(y); if(fx!=fy)pre[fx]=fy; } int main() { int n,m; while(scanf("%d%d",&n,&m) && (n&&m)) { init(); for(int i=1; i<=n; i++)pre[i]=i; for(int i=1; i<=m; i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); addedge(u,v,w); addedge(v,u,w); join(u,v); } int flag=0; for(int i=1; i<=n; i++) if(Find(i)!=Find(1))flag=1; if(flag)printf("0\n"); else { printf("%d\n",solve(n)); } } return 0; } /* 5 2 4 3 0 4 5 0 0 0 1 0 */