题目大意：给一些点，用一些边把这些点相连，每一条边上有一个权值。现在要你破坏任意一个边（要付出相应边权值的代价），使得至少有两个连通块。输出最小代价值。
算法思路：这题坑多，要考虑仔细：
1.图是边双连通图，就做不到删除一边得到两个连通块，这种情况输出-1.
2.图是连通但不边双联通，就用tarjan找出桥中权值最小的，这里有个巨坑，如果桥最小的权值为0，这时根据题意，要输出1而不是0（看看题就能理解）。
3.图不是连通的，就不需要去删边，即直接输出0。
4.还要注意，输入的边有可能出现重边，这个要特殊标记下。
至于求桥就用tarjan算法就可以标记出。
#include#include #include #include #include #include #include #include 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\n"); continue; } if(!flag){ //图是边双连通的 printf("-1\n"); } else{ if(Min == 0) printf("1\n"); else printf("%d\n",Min); } }}