Caocao's Bridges---hdu4738（桥）

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

题就是求出所有的桥，然后输出桥的权值的最小值。

如果一开始是不连通的，输出0.

图有重边，需要处理， 不能用邻接矩阵。、、、因为邻接矩阵不能表示两点之间有2条路，如果有两条路就不能算是桥；

还有如果取到的最小值是0的话，要输出1，表示要派一个人过去。

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<queue>
#include<algorithm>
using namespace std;
#define N 1100
#define INF 0xfffffff

struct node
{
    int x,y;
} bridge[N];
struct Edge
{
    int v, c, next;
} e[N*N];
int low[N], cnt, dfn[N], n, m, f[N], maps[N][N], head[N], Min;
int Time, nBridge;
void Init()
{
    Time = cnt = nBridge = 0;
    memset(low, 0, sizeof(low));
    memset(dfn, 0, sizeof(dfn));
    memset(bridge, 0, sizeof(bridge));
    memset(f, 0, sizeof(f));
    memset(maps, -1, sizeof(maps));
    memset(head, -1, sizeof(head));
}
void add(int u, int v, int c)
{
    e[cnt].v = v;
    e[cnt].c = c;
    e[cnt].next = head[u];
    head[u] = cnt++;
}
void Tajar(int u, int father)
{
    f[u]=father;
    low[u]=dfn[u]=++Time;
    int k=0;
    for(int i=head[u]; i!=-1; i=e[i].next)
    {
        int v=e[i].v;
        if(father==v&&!k)
        {
            k++;
            continue;
        }
        if(!dfn[v])
        {
            Tajar(v, u);
            low[u]=min(low[u],low[v]);
            if(low[v]>dfn[u])
                Min=min(Min, e[i].c);
        }
        else
        {
            low[u]= min(low[u], dfn[v]);
        }

    }
}

int main()
{
    int a,b,c;
    while(scanf("%d %d",&n,&m), n+m)
    {
        Init();
        for(int i=1; i<=m; i++)
        {
            scanf("%d %d %d",&a,&b,&c);
            add(a, b, c);
            add(b, a, c);
        }
        int k=0;
        Min=INF;
        for(int i=1; i<=n; i++)
        {
            if(!dfn[i])
            {
                Tajar(i,-1);
                k++;
            }
        }
        if(k>1)
        {
            printf("0
");
            continue;
        }
        if(Min==0)
            Min=1;
        else if(Min==INF)
            Min=-1;
        printf("%d
", Min);
    }
    return 0;
}