刚拿到这道题时挺有思路，无奈平日里只敲过找割顶的代码，判桥的代码当时自己也没仔细敲。
当时一把泪啊，忽然感觉自己的图论才只是刚搞了个起步啊。。
题目有神坑。 就是先判是否连通，不连通直接输出0;
还有一个比较坑的是有重边的情况，那这样就有重边的两点之间就不可能存在桥。
再就是桥上无士兵把守也要派一个人去炸。
。。。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std; const int maxn = 1500;
int dfs_clock, current_clock, ans, current_cc;
int adj[maxn][maxn], iscut[maxn], vis[maxn], pre[maxn], low[maxn];
vector<int> G[maxn];
int n, m, a, b, c, INF = 10000000; void dfs(int u)
{
vis[u] = 1;
//PREVISIT(u); 访问u之前的操作
for(int i = 0; i < G[u].size(); i++)
{
int v = G[u][i];
if(!vis[v]) dfs(v);
}
//POSTVISIT(u); 访问结点u之后的操作
} void find_cc() //给连通分量标号
{
current_cc = 0;
memset(vis, 0, sizeof(vis));
for(int u = 1; u <= n; u++) if(!vis[u])
{
current_cc++;
dfs(u);
}
} int dfs_bridge(int u,int fa) //u在dfs树中的父结点是fa
{
int lowu = pre[u] = ++dfs_clock;
int child = 0; //子结点数目
for(int i = 0; i < G[u].size(); i++)
{
int v = G[u][i];
if(!pre[v]) //没有访问过v
{
child++;
int lowv = dfs_bridge(v, u);
lowu = min(lowu, lowv);
if(lowv >= pre[u])
{
iscut[u] = true; //割点判断
if(lowv > pre[u] && adj[u][v] != -2) //桥的判断可以相应灵活处理
ans = min(ans, adj[u][v]);
}
}
else if(pre[v] < pre[u] && v != fa)
lowu = min(lowu, pre[v]); //用反向边更新u的low函数
}
if(fa < 0 && child == 1)
{
// 但是不用加是否单独判桥的判断？
iscut[u] = 0; //应该是避免单结点判桥、割顶的情况吧
}
low[u] = lowu;
return lowu;
} void init()
{
memset(pre, 0, sizeof(pre));
memset(iscut, 0, sizeof(iscut));
memset(adj, -1 ,sizeof(adj));
for(int i = 0; i <= n; i++)
G[i].clear();
} int main()
{
while(scanf("%d%d",&n, &m) != EOF)
{
if(!n && !m) break;
init();
while(m--)
{
scanf("%d%d%d", &a, &b, &c);
if(adj[a][b] == -1)
{
G[a].push_back(b);
G[b].push_back(a);
adj[a][b] = c;
adj[b][a] = c;
}
else // 两点之间有两条边肯定不可能是桥
{
adj[a][b] = -2;
adj[b][a] = -2;
}
} ans = INF;
dfs(1); find_cc();
//printf("~%d\n",current_cc);
if(current_cc >= 2) { printf("0\n"); continue;}
else dfs_bridge(1, -1);
if(ans == 0) printf("1\n");
else if(ans == INF ) printf("-1\n");
else printf("%d\n", ans);
}
return 0;
}