hdu 4738 Caocao's Bridges（桥的最小权值+去重）

http://acm.hdu.edu.cn/showproblem.php?pid=4738

题目大意：曹操有一些岛屿被桥连接，每座都有士兵把守，周瑜想把这些岛屿分成两部分，但他只能炸毁一条桥，问最少需要派几个士兵去;如果不能完成输出-1

1：如果这些岛屿不连通，则不需要派人前去

2：如果桥的守卫是0的话也得派一人去炸毁

3：如果不能完成输出-1

4：输出最少需派的人数

#include<stdio.h>

#include<string.h>

#include<math.h>

#include<queue>

#include<algorithm>

using namespace std;

#define N 1100

#define INF 0xfffffff

int dfn[N], low[N], head[N], f[N];

int Time, m, n, Min, cnt;

struct Edge

{

    int next, u, v, c;

} edge[N * N];

void Init()

{

    memset(head, -, sizeof(head));

    memset(dfn, , sizeof(dfn));

    memset(low, , sizeof(low));

    memset(f, , sizeof(f));

    Time = cnt = ;

}

void AddEdge(int u, int v, int c)

{

    edge[cnt].u = u;

    edge[cnt].v = v;

    edge[cnt].c = c;

    edge[cnt].next = head[u];

    head[u] = cnt++;

}

void Tarjan(int u, int fa)

{

    int i, v, flag = ;

    low[u] = dfn[u] = ++Time;

    f[u] = fa;

    for(i = head[u] ; i != - ; i = edge[i].next)

    {

        v = edge[i].v;

        if(v == fa && !flag)

        {

            flag = ;

            continue;

        }//去重边，如果有重边则跳过

        if(!dfn[v])

        {

            Tarjan(v, u);

            low[u] = min(low[u], low[v]);

            if(dfn[u] < low[v])

                Min = min(Min, edge[i].c);

        }

        else

            low[u] = min(low[u], dfn[v]);

    }

}

int main()

{

    int i, u, v, c, k;

    while(scanf("%d%d", &m, &n), m + n)

    {

        Init();

        k = ;

        while(n--)

        {

            scanf("%d%d%d", &u, &v, &c);

            AddEdge(u, v, c);

            AddEdge(v, u, c);

        }

        Min = INF;

        for(i =  ; i <= m ; i++)

        {

            if(!dfn[i])

            {

                Tarjan(i, -);

                k++;

            }

        }

        if(k > )

        {

            printf("0\n");

            continue;

        }//

        if(Min == )

            printf("1\n");//

        else if(Min == INF)

            printf("-1\n");//

        else

            printf("%d\n", Min);//

    }

    return ;

}