<题目链接>
题目大意：
曹操在长江上建立了一些点，点之间有一些边连着。如果这些点构成的无向图变成了连通图，那么曹操就无敌了。周瑜为了防止曹操变得无敌，就打算去摧毁连接曹操的点的桥。但是诸葛亮把所有炸弹都带走了，只留下一枚给周瑜。所以周瑜只能炸一条桥。
题目给出n，m。表示有n个点，m条桥。
接下来的m行每行给出a，b，c，表示a点和b点之间有一条桥，而且曹操派了c个人去守卫这条桥。
现在问周瑜最少派多少人去炸桥。
如果无法使曹操的点成为多个连通图，则输出-1.
解题思路：
就是用Tarjan找出图中所有的桥，并且不断更新所有桥上防守人数最少的值。
需要注意几点：
1.首先先判断整张图是否为连通图，如果不为连通图，则无需派人去炸桥；
2.如果原图不存在桥，即，只炸毁一条边不能够破坏原图的连通性，就直接输出-1；
3.如果防守人数最少的那个桥上的防守人数为0，也需要派人去炸桥，因为那座桥不会自动毁坏。
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
const int maxn = ;
const int INF = 0x3f3f3f3f;
struct node{
int to,cost,next;
};
node edge[maxn*maxn];
int head[maxn],n,m,num,ans,sum,dfn[maxn],child,low[maxn];
void addedge(int u,int v,int c){ //双向存图
edge[num].to=v;edge[num].cost=c;edge[num].next=head[u];
head[u]=num++;
edge[num].to=u;edge[num].cost=c;edge[num].next=head[v];
head[v]=num++;
}
void tarjan(int u,int fa){
child++; //child记录连通到的点的数量
low[u]=dfn[u]=sum++;
for(int i=head[u];i!=-;i=edge[i].next){
int v=edge[i].to;
if(i==(fa^)) continue; //标记反向边
if(!dfn[v]){
tarjan(v,i);
low[u]=min(low[u],low[v]);
if(dfn[u]<low[v]){ //桥的判定方法 因为low[v]<dfn[u]，说明v和u不属于同一联通块，并且v不能通过u-v之间的边到达比low[v]小的点，说明这条边为桥
ans=min(ans,edge[i].cost); //更新权值最小的桥
}
}
else low[u]=min(low[u],dfn[v]);
}
} int main(){
int a,b,c;
while(~scanf("%d%d",&n,&m),n||m){
memset(head,-,sizeof(head));
memset(dfn,,sizeof(dfn));
memset(low,,sizeof(low));
ans=INF;child=;sum=;
for(int i=;i<=m;i++){
scanf("%d%d%d",&a,&b,&c);
addedge(a,b,c);
}
tarjan(,-);
if(child<n) printf("0\n"); //如果原图本来就不是连通图，就直接输出0即可
else if(ans==INF)printf("-1\n"); //如果没有桥，即，只派出一个人不能将原图的连通性破坏，就直接输出-1
else if(ans==) printf("1\n"); //如果桥上无人防守，也需要派人去把那座桥炸毁
else printf("%d\n",ans);
}
return ;
}
2018-08-17