Caocao's Bridges
题意：给个无向图，求出边权最小的桥。
一看，直接缩点，若无桥，输出-1，有桥，遍历下边，更新最小。。分分钟搞定，以为IA的。。一交wa。。。
坑点：1：若原图不连通，则无须派人去！输出0！；
2：若桥的权是0，则还有派一个人把炸弹拿去，输出1！
3：有重边。（按多条边算）。
哎！记住这个教训！以后做题
1：考虑边界或者特殊数据！（边权为0！n==1等）
2：考虑原图连通性！（这次考虑了原图就强连通。。没有考虑根本不连通！）
3：重边。这题的重边是按重边算（不是一条），而我采用的数据结构和算法恰好回避了这个问题（我用链式前向星和无向图自创tarjan模板可以重边按多边算（重边的点必在一个BCC中），若要重边按一条算，则用链星和第二套记录父亲点法tarjan来）。
这题WA真正元凶：不可原谅自己！在用e[i][0]时候，竟然又犯低级错误！！！i用边啊！用什么点!!!
#include<iostream>
#include<stack>
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxv=1005,maxe=1000*1003;
int nume=0;int head[maxv];int e[maxe][3];
void inline adde(int i,int j,int c)
{
e[nume][0]=j;e[nume][1]=head[i];head[i]=nume;
e[nume++][2]=c;
e[nume][0]=i;e[nume][1]=head[j];head[j]=nume;
e[nume++][2]=c;
}
int dfn[maxv];int low[maxv];int vis[maxv];int ins[maxv]; stack<int>sta;
int bcc[maxv];int numb=0;int times=0; int vise[maxe];
int n,m;
void tarjan(int u)
{
dfn[u]=low[u]=times++;
ins[u]=1;
sta.push(u);
for(int i=head[u];i!=-1;i=e[i][1])
{
if(vise[i])continue;
int v=e[i][0];
if(!vis[v])
{
vis[v]=1;
vise[i]=vise[i^1]=1;
tarjan(v);
if(low[v]<low[u])low[u]=low[v];
}
else if(ins[v]&&dfn[v]<low[u])
{
low[u]=dfn[v];
}
}
if(low[u]==dfn[u])
{
numb++;
int cur;
do
{
cur=sta.top();
sta.pop();
ins[cur]=0;
bcc[cur]=numb;
}while(cur!=u);
}
}
void solve()
{
int marks=0;
for(int i=1;i<=n;i++)
{
if(!vis[i])
{
vis[i]=1;
tarjan(i);
marks++;
}
}
if(marks>=2) //坑1
{
printf("0
");return ;
}
if(numb==1)
{
printf("-1
");return ;
}
int mins=inf;
for(int i=1;i<=n;i++)
for(int j=head[i];j!=-1;j=e[j][1])
{
if(bcc[i]!=bcc[e[j][0]]) //e[j][0]竟然写成e[i][0]!!!sb!!
{
if(e[j][2]<mins)mins=e[j][2];
}
}
if(mins==0)mins=1; //坑2
printf("%d
",mins);
}
void read_build()
{
int aa,bb,cc;
for(int i=0;i<m;i++)
{
scanf("%d%d%d",&aa,&bb,&cc);
adde(aa,bb,cc);
}
}
void init()
{
numb=times=nume=0;
memset(vise,0,sizeof(vise));
for(int i=0;i<maxv;i++)
{
head[i]=-1;ins[i]=dfn[i]=low[i]=bcc[i]=vis[i]=0;
}
}
int main()
{
while(~scanf("%d%d",&n,&m)&&(n||m))
{
init();
read_build();
solve();
}
return 0;
}