题目链接：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 = ;
const int maxe = 1e6+;
const int INF = 0x3f3f3f3f; //边的双连通分量
int pre[maxn],low[maxn],dfs_clock; struct Edge{
int u,v,w;
int next;
}edges[maxe*];
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!=-;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] == ) { //要判断没有重边
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,,sizeof(pre));
memset(head,-,sizeof(head));
memset(G,,sizeof(G));
cnt = ;
dfs_clock = ;
for(int i=;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(,-); bool f = ;
for(int i=;i<=N;i++){
if(!pre[i]){
f = true;
break;
} }
if(f){ //图不是连通的
printf("0\n");
continue;
} if(!flag){ //图是边双连通的
printf("-1\n");
}
else{
if(Min == ) printf("1\n");
else printf("%d\n",Min);
}
} }