hdu4738（割桥）

找人去炸边，炸完之后分成两个连通块（炸割桥）

每条边上有w个守卫，派去炸桥的人不能比守卫少

所以，

如果原本不连通，那么输出0

如果没有桥，输出-1

如果有桥没有守卫，那么是输出1，而不是0（trick）

 #pragma warning(disable:4996)

 #pragma comment(linker, "/STACK:1024000000,1024000000")

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 #include <vector>

 #include <stack>

 #include <queue>

 #include <math.h>

 #include <algorithm>

 #include <map>

 #include <set>

 #include <functional>

 using namespace std;

 const int INF =  << ;

 typedef __int64 LL;

 /*

 要摧毁的边只能是桥

 */

 const int N =  + ;

 int head[N], next[N*N], to[N*N], dist[N*N], e;

 int dfn[N], low[N], dfs_clock, ans;

 void init()

 {

     memset(head, -, sizeof(head));

     memset(dfn, , sizeof(dfn));

     memset(low, , sizeof(low));

     dfs_clock = e = ;

     ans = INF;

 }

 void addEdge(int u, int v, int dis)

 {

     to[e] = v;

     dist[e] = dis;

     ::next[e] = head[u];

     head[u] = e++;

 }

 void tarjan(int u, int fa)

 {

     dfn[u] = low[u] = ++dfs_clock;

     bool flag = false;

     for (int i = head[u]; i + ; i = ::next[i])

     {

         if (to[i] == fa && !flag)

         {

             flag = true;

             continue;

         }

         if(dfn[to[i]]==)

             tarjan(to[i], u);

         low[u] = min(low[to[i]], low[u]);

         if (low[to[i]] > dfn[u])

             ans = min(ans, dist[i]);

     }

 }

 int main()

 {

     int n, m;

     while (scanf("%d%d", &n, &m),n+m)

     {

         int u, v, dis;

         init();

         for (int i = ;i <= m;++i)

         {

             scanf("%d%d%d", &u, &v, &dis);

             addEdge(u, v, dis);

             addEdge(v, u, dis);

         }

         ans = INF;

         tarjan(, -);

         bool flag = true;

         for (int i = ;i <= n;++i)

             if (dfn[i] == )

             {

                 printf("0\n");

                 flag = false;

                 break;

             }

         if (!flag)continue;

         if (ans == INF)

             ans = -;

         if (ans == )ans = ;

         printf("%d\n", ans);

     }

     return ;

 }