1 n 为顶点数 下标从0 开始
2 O(V3)
3 DFS判连通
4 边权为1时 即是求边连通度
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 512;
const int INF = 1 << 29;
int n, m, g[N][N];
bool flag[N];
int cnt;
void Merge(int a, int b)
{
     for (int i = 0; i < n; ++ i)
     {
         g[i][a] += g[i][b];
         g[a][i] += g[b][i];
     }
     for (int i = 0; i < n; ++ i)
     {
         g[i][b] = g[i][n-1];
         g[b][i] = g[n-1][i];
     }
     g[a][a] = 0;
     -- n;
}
int MinCut()
{
     int cut = INF, d[N], w[N];
     bool seta[N];
     while ( n != 1 )
     {
         memset(seta, false, sizeof(seta));
         memset(w, 0, sizeof(w));
         for (int i = 0; i < n; i++)
         {
             int mw = -INF, mi;
             for (int j = 0; j < n; j++)
                 if (!seta[j] && mw < w[j])
                     mw = w[j], mi = j;
             d[i] = mi;
             seta[mi] = true;
             for (int j = 0; j < n; j++)
                 if (!seta[j]) w[j] += g[mi][j];
         }
         cut <?= w[d[n-1]];
         Merge(d[n-2], d[n-1]);
     }
     return cut;
}
void DFS(int u)
{
     flag[u] = true;
     ++ cnt;
     for (int i = 0; i < n; ++ i)
         if (g[u][i] && !flag[i]) DFS(i);
}
int main()
{
     int i, j, k;
     while ( scanf("%d %d", &n, &m) == 2 )
     {
         memset(g, 0, sizeof(g));
         while ( m -- )
         {
             scanf("%d %d %d", &i, &j, &k);
             g[i][j] += k;
             g[j][i] = g[i][j];
         }
         memset(flag, false, sizeof(flag));
         cnt = 0;
         DFS(0);
         if (cnt < n)
         {
             printf("0\n");
             continue;
         }
         printf("%d\n", MinCut());
     }
     return 0;
}

……

...

......