HDU 4738 Caocao's Bridges（求价值最小的桥）

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<string>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<bitset>
using namespace std;
#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )
#define CLEAR( a , x ) memset ( a , x , sizeof a )
typedef long long LL;
typedef pair<int,int>pil;
const int maxn=1000+10;
const int maxm=maxn*maxn;
struct node{
    int to,next;
    int val;
    bool col;//为桥
}e[maxm];
int head[maxn],cnt,cntE;
int DFN[maxn],low[maxn];
int s[maxn],instack[maxn];
int idex,top,bridge;
int belong[maxn],f[maxn];
int col[maxn],add[maxn];
int n,m;
void init()
{
    cnt=top=idex=bridge=cntE=0;
    CLEAR(head,-1);
    CLEAR(DFN,0);
    CLEAR(low,0);
    CLEAR(instack,0);
    CLEAR(belong,0);
    CLEAR(f,-1);
}
void addedge(int u,int v,int w)
{
    e[cntE].to=v;e[cntE].next=head[u];
    e[cntE].val=w;
    e[cntE].col=false;head[u]=cntE++;
}
void Tarjan(int u,int pre)
{
    low[u]=DFN[u]=++idex;
    s[top++]=u;
    instack[u]=1;
    int son=0;
    int pre_num=0;
    for(int i=head[u];i!=-1;i=e[i].next)
    {
        int v=e[i].to;
        if(v==pre&&!pre_num)
        {
            pre_num++;
            continue;
        }
        if(!DFN[v])
        {
            son++;
            Tarjan(v,u);
            if(low[u]>low[v]) low[u]=low[v];
            if(low[v]>DFN[u])//桥
            {
                bridge++;
                e[i].col=true;
                e[i^1].col=true;
            }
            if(u!=pre&&low[v]>=DFN[u])//割点判断1
            {
                col[u]=1;
                add[u]++;
            }
        }
        else if(low[u]>DFN[v])
            low[u]=DFN[v];
    }
    if(u==pre&&son>1)  col[u]=1;//割点判断2
    if(u==pre)  add[u]=son-1;
    instack[u]=0;
    top--;
}
void work()
{
    REPF(i,1,n)
       if(!DFN[i])  Tarjan(i,i);
    int minn=0x3f3f3f3f;
    REPF(u,1,n)
    {
        for(int i=head[u];i!=-1;i=e[i].next)
            if(e[i].col&&minn>e[i].val)  minn=e[i].val;
    }
    if(minn==0)  puts("1");
    else if(minn==0x3f3f3f3f)  puts("-1");
    else  printf("%d\n",minn);

}
int find(int x)
{
    if(f[x]==-1)  return x;
    else  return f[x]=find(f[x]);
}
void Union(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x!=y)  f[x]=y;
}
int main()
{
    int u,v,w;
    while(~scanf("%d%d",&n,&m)&&(n+m))
    {
        init();
        REPF(i,1,m)
        {
            scanf("%d%d%d",&u,&v,&w);
            addedge(u,v,w);
            addedge(v,u,w);
            Union(u,v);
        }
        int flag=1;
        REPF(i,1,n)
            if(find(i)!=find(1))  flag=0;
        if(!flag)
        {
            puts("0");
            continue;
        }
        work();
    }
    return 0;
}