题目:hdu 4738
题目意思： 曹操有N个岛，这些岛用M座桥连接起来
每座桥有士兵把守(也可能没有)
周瑜想让这N个岛不连通，但只能炸掉一座桥
并且炸掉一座桥需要派出不小于守桥士兵数的人去
解题思路: 首先判断图是否连通，不连通则不需要去炸桥，输出0
图连通，则可以用Tarjan找割边
割边不存在输出-1表示不能达到目的
找到所有的割边，只需要炸掉其中守兵数最少的桥即可
PS: 桥的守兵数为0时，也需要派出一个人去
还要注意一下重边的问题，是重边的话一定不是桥，我用邻接表记录的，是重边的话 我就距离变成INF
#include<bits/stdc++.h>
#define mod 1000000007
#define mem(a) memset(a,0,sizeof(a));
typedef long long ll;
const int INF=0x3f3f3f3f;
using namespace std;
int vim[],dfn[];
vector<int>q[];
int jg[][];
int ans;
int top;
void tarjan(int x,int fa)
{ vim[x]=dfn[x]=++top;
for(int i:q[x])
{ if(i==fa)continue;
if(!dfn[i])
{
tarjan(i,x);
vim[x]=min(vim[i],vim[x]);
// cout<<vim[i]<<" "<<dfn[x]<<endl;
if(vim[i]>dfn[x])
{
ans=min(ans,jg[x][i]);
}
}
else
{
vim[x]=min(vim[x],dfn[i]);
}
} }
int main()
{
int n,m;
while(cin>>n>>m&&n+m){
ans=INF;mem(vim);mem(dfn);
for(int i=;i<=n;i++)
q[i].clear();
memset(jg,,sizeof(jg));
for(int i=;i<=m;i++)
{
int a,b,c;
cin>>a>>b>>c;
q[a].pb(b);
q[b].pb(a);
if(!jg[a][b]){
jg[a][b]=jg[b][a]=c;}
else { jg[a][b]=jg[b][a]=INF;
}
}
int q=;
for(int i=;i<=n;i++)
if(!dfn[i])
tarjan(i,),q++;
if(q>)cout<<<<endl;
else if(ans==INF)cout<<-<<endl;
else if(!ans)cout<<<<endl;
else cout<<ans<<endl;
}}