hdu 4738 Caocao's Bridges (tarjan求桥)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4738

题目大意：给一些点，用一些边把这些点相连，每一条边上有一个权值。现在要你破坏任意一个边（要付出相应边权值的代价），使得至少有两个连通块。输出最小代价值。

算法思路：这题坑多，要考虑仔细：

1.图是边双连通图，就做不到删除一边得到两个连通块，这种情况输出-1.    

2.图是连通但不边双联通，就用tarjan找出桥中权值最小的，这里有个巨坑，如果桥最小的权值为0，这时根据题意，要输出1而不是0（看看题就能理解）。  

3.图不是连通的，就不需要去删边，即直接输出0。

4.还要注意，输入的边有可能出现重边，这个要特殊标记下。

至于求桥就用tarjan算法就可以标记出。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
#include <utility>
using namespace std;

const int maxn = 1055;
const int maxe = 1e6+100;
const int INF  = 0x3f3f3f3f;


//边的双连通分量
int pre[maxn],low[maxn],dfs_clock;

struct Edge{
    int u,v,w;
    int next;
}edges[maxe*2];
int head[maxn],cnt;

bool flag;
int Min;
int G[maxn][maxn];


void addedge(int u,int v,int w){
    edges[cnt].u = u;edges[cnt].v = v;edges[cnt].w = w;edges[cnt].next = head[u];
    head[u] = cnt++;
    edges[cnt].u = v;edges[cnt].v = u;edges[cnt].w = w;edges[cnt].next = head[v];
    head[v] = cnt++;
}
void tarjan(int u,int fa){
    pre[u] = low[u]  =  dfs_clock++;
    for(int i=head[u];i!=-1;i=edges[i].next){
        int v = edges[i].v;
        if(!pre[v]){
            tarjan(v,u);
            low[u] = min(low[u],low[v]);
            if(low[v] > pre[u] && G[u][v] == 1) { //要判断没有重边
                flag = true;
                Min = min(Min,edges[i].w);
            }
        }
        else if(pre[v] < pre[u] && v != fa)   //u->v是反向边；
            low[u] = min(low[u],pre[v]);
    }
}


int main()
{
    //freopen("E:\acm\input.txt","r",stdin);

    int N,M;
    while(cin>>N>>M && N+M){
        memset(pre,0,sizeof(pre));
        memset(head,-1,sizeof(head));
        memset(G,0,sizeof(G));
        cnt = 0;
        dfs_clock = 1;
        for(int i=1;i<=M;i++){
            int u,v,w;

            scanf("%d %d %d",&u,&v,&w);
            G[u][v]++;  //标记是否出现重边
            G[v][u]++;
            addedge(u,v,w);
        }
        Min = INF;
        flag = false;
        tarjan(1,-1);

        bool f = 0;
        for(int i=2;i<=N;i++){
            if(!pre[i]){
                f = true;
                break;
            }

        }
        if(f){  //图不是连通的
            printf("0
");
            continue;
        }

        if(!flag){ //图是边双连通的
            printf("-1
");
        }
        else{
            if(Min == 0)  printf("1
");
            else          printf("%d
",Min);
        }
    }

}