hdu 4738 Caocao's Bridges tarrjan

Caocao's Bridges
Time Limit：20 Sec
メモリLimit:256 MB
タイトル接続
http://acm.hdu.edu.cn/showproblem.php?pid=4738
Description
Caocao was defeated by Zhuge Liang and Zhou Yu in t he battle of Chibi.But he wouldn't give up.Caocao's army still was not good water battles、so he came up with another der.Hethmand.bulandCaocao's army could easure atck Zhoo's trop.Caocao also built bridges connecting islands.If all island wers connected by bridges、Caocao's army could d d deployed veryventinghone.land。so he wanted to destroy some Caocao's bridges so one or more island would be seperated from other islands.But Zhou Yu had onlyone bomb which was left by Zhuge Liang，so he could only destroy one bridge.Zhou Yu must send someone carrying the bomb to destroy the bridge.The e e might be gurds on bridges.The so so so so so must send some carrying the bomb't be less the bridnor the mission would fail.Please figure out as least how many solders Zhou Yu have to complette the island seperating mission.
Input
The re re no more than 12 test cases.
In each test case:
The first line contains two integers，N and M，meaning that there are N islands and M bridges.All the islands are numberred from 1 to N.（2==N<=1000，0==N 2）
Next M line describes M bridges.Each line contains three integers U，V and W，meaning that there is a bridge connecting island V，and there are W Grands on that bridge.（U≠V and 0<=W=10）
The input ends with N=0 and M=0.
Output
For each test case，print the minimum soure number Zhou Yu to send to complette e the mission.If Zhou Yu couldn't succered any way，prinstead-1.
Sample Input
3 31 2 72 3 43 1 43 1 2 72 3 40。
Sample Output
-14
HINT
 
題意
どの辺にも権利があります。橋を爆破したいです。最低何人を派遣すれば、この図がつながりません。
クイズ:
裸のタラジャンが橋を探す
1.重さがある
2.この図は最初はつながらない
3.橋辺権は0で、一人で爆弾を送る必要があります。
コード

#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <queue>
#include <typeinfo>
#include <fstream>
#include <map>
#include <stack>
typedef long long ll;
using namespace std;
//freopen("D.in","r",stdin);
//freopen("D.out","w",stdout);
#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)
#define test freopen("test.txt","r",stdin)
const int maxn=1100;
const int maxm=2100000;
#define mod 1000000009
#define eps 1e-9
const int inf=0x3f3f3f3f;
const ll infll = 0x3f3f3f3f3f3f3f3fLL;
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
//**************************************************************************************
struct EDGE{
    int v,next,w;
}E[maxm];
int head[maxn],tot;
int low[maxn],dfn[maxn];
int kiss;
int ans;
int n,m,u,v,w;
void Init()
{
    memset(head,-1,sizeof head);
    tot=0;
    memset(low,0,sizeof low);
    memset(dfn,0,sizeof dfn);
    kiss=0;
    ans=inf;
}

void add_edge(int u,int v,int w){
    E[tot].w=w;
    E[tot].v=v;
    E[tot].next=head[u];
    head[u]=tot++;
}

void Tarjan(int u,int pre)
{
    dfn[u]=low[u]=++kiss;
    int v;
    for(int i=head[u];i!=-1;i=E[i].next)
    {
        if(i==(pre^1))continue;
        v=E[i].v;
        if(!dfn[v])
            {
            Tarjan(v,i);
            if(low[v]<low[u])
                low[u]=low[v];
            if(low[v]>dfn[u])
                ans=min(ans,E[i].w);
        }else if(dfn[v]<low[u])
            low[u]=dfn[v];
    }
}

int main(){

    while(scanf("%d %d",&n,&m)!=EOF)
    {
        if(n==0&&m==0)break;
        Init();
        for(int i=1;i<=m;i++)
        {
            scanf("%d %d %d",&u,&v,&w);
            add_edge(u,v,w);
            add_edge(v,u,w);
        }
        int cnt=0;
        for(int i=1;i<=n;i++)
            if(!dfn[i]){
                cnt++;
                Tarjan(i,-1);
            }
        if(cnt>1)
            ans=0;
        else if(ans==inf)
            ans=-1;
        else if(ans==0)
            ans=1;
        printf("%d
",ans);
    }
    return 0;
}