传送门：Caocao's Bridges
题意：n个岛，曹操在一些岛之间建了一些桥，每个桥上有一些士兵把守，周瑜只有一个炸弹只能炸掉一个桥，并能使一些岛被孤立出来，炸弹需要士兵带过去，士兵的数量不能小于目标桥的守卫，求出最少要派出多少士兵。
分析：题目很明显要找出边权最小的桥，但本题有几个坑：
1）图若不连通，不需要派人过去。
2）当桥边权为0时，必须派一个人过去。
#pragma comment(linker,"/STACK:1024000000,1024000000")
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdlib>
#include <stack>
#include <vector>
#include <set>
#include <map>
#define LL long long
#define mod 100000000
#define inf 0x3f3f3f3f
#define eps 1e-6
#define N 1010
#define FILL(a,b) (memset(a,b,sizeof(a)))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define PII pair<int,int>
using namespace std;
struct edge
{
int v,w,next;
edge(){}
edge(int v,int w,int next):v(v),w(w),next(next){}
}e[N*N<<];
int n,step,scc,top,tot,ans;
int head[N],dfn[N],low[N],belong[N],Stack[N];
bool instack[N],vis[N*N<<];
void init()
{
tot=;top=;scc=;ans=inf;
FILL(head,-);FILL(dfn,);
FILL(low,);FILL(instack,false);
FILL(vis,false);
}
void addedge(int u,int v,int w)
{
e[tot]=edge(v,w,head[u]);
head[u]=tot++;
}
void tarjan(int u)
{
int v;
dfn[u]=low[u]=++step;
Stack[top++]=u;
instack[u]=true;
for(int i=head[u];~i;i=e[i].next)
{
v=e[i].v;
if(vis[i])continue;
vis[i]=vis[i^]=true;
if(!dfn[v])
{
tarjan(v);
if(low[u]>low[v])low[u]=low[v];
if(dfn[u]<low[v])
{
ans=min(ans,e[i].w);
}
}
else if(instack[v])
{
if(low[u]>dfn[v])low[u]=dfn[v];
}
}
if(dfn[u]==low[u])
{
scc++;
do
{
v=Stack[--top];
instack[v]=false;
belong[v]=scc;
}while(v!=u);
}
} void solve()
{
int num=;
for(int i=;i<=n;i++)
if(!dfn[i])
{
tarjan(i);
num++;
}
if(num>)
{
puts("");
return;
}
if(ans==inf)puts("-1");
else
{
if(ans==)puts("");
else printf("%d\n",ans);
}
}
int main()
{
int m,u,v,w;
while(scanf("%d%d",&n,&m)>)
{
if(n+m==)break;
init();
for(int i=;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&w);
addedge(u,v,w);
addedge(v,u,w);
}
solve();
}
}