细节题: 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);
- }
- }
来源: http://www.bubuko.com/infodetail-2974361.html