细节题：1.如果图不连通，则输出0
2.如果图没有桥，本身是双联通图，则输出-1
3.如果最小的桥权值为0，任然要输出1
#include<bits/stdc++.h> using namespace std; #define maxn 1005 #define maxm 1005*1005 struct Edge{int to,nxt,w,cut;}edge[maxm<<1]; int n,m,head[maxn],tot,ans; int dfn[maxn],low[maxn],ind; void tarjan(int u,int in_edge){ dfn[u]=low[u]=++ind; for(int i=head[u];i!=-1;i=edge[i].nxt){ int v=edge[i].to; if(!dfn[v]){ tarjan(v,i); low[u]=min(low[u],low[v]); if(low[v]>dfn[u]) ans=min(ans,edge[i].w); } else if(i!=(in_edge^1)) low[u]=min(low[u],dfn[v]); } } void init(){ ind=tot=0; memset(head,-1,sizeof head); memset(dfn,0,sizeof dfn); memset(low,0,sizeof low); } void addedge(int u,int v,int w){ edge[tot].to=v; edge[tot].nxt=head[u]; edge[tot].w=w; head[u]=tot++; } int main(){ while(cin>>n>>m,n+m){ init(); while(m--){ int u,v,w; scanf("%d%d%d",&u,&v,&w); addedge(u,v,w); addedge(v,u,w); } ans=0x3f3f3f3f; int flag=0; for(int i=1;i<=n;i++) if(!dfn[i]) flag++,tarjan(i,0); if(ans==0)ans++; if(flag>1) puts("0"); else if(ans==0x3f3f3f3f) puts("-1"); else printf("%d\n",ans); } }
转载于:https://www.cnblogs.com/zsben991126/p/10464120.html
