全局最小割，和PKU 2914 minimun cut一樣。直接上模板。
#include <stdio.h>
#include <string.h>
#define N 155
#define INF 1 << 28
#define MIN(a, b) (a < b ? a : b)
int g[N][N], w[N];
bool visit[N], del[N];
int Stoer_Wagner(int n)
{
int mincut = INF;
int st = 1;
memset(del, 0, sizeof(del));
for(int i = 1; i < n; i++)
{
for(int j = 1; j <= n; j++)
if(!del[j])
{
w[j] = g[st][j];
}
int mmin, cur = st, pre;
memset(visit, 0, sizeof(visit));
visit[st] = 1;
for(int j = 1; j <= n - i; j++)
{
mmin = -INF, pre = cur, cur = 0;
for(int k = 1; k <= n; k++)
if(!del[k] && !visit[k] && w[k] > mmin)
{
cur = k;
mmin = w[k];
}
if(!cur) return 0;
visit[cur] = 1;
for(int k = 1; k <= n; k++)
if(!del[k] && !visit[k])
{
w[k] += g[cur][k];
}
}
mincut = MIN(mincut, w[cur]);
del[cur] = 1;
for(int j = 1; j <= n; j++)
if(!del[j] && j != pre)
{
g[j][pre] += g[j][cur];
g[pre][j] += g[cur][j];
}
}
return mincut;
}
int main()
{
int cas = 1, t, n, m;
scanf("%d", &t);
while(t--)
{
scanf("%d %d", &n, &m);
memset(g, 0, sizeof(g));
for(int i = 0; i < m; i++)
{
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
g[a][b] += c;
g[b][a] += c;
}
printf("Case #%d: %d\n", cas++, Stoer_Wagner(n));
}
return 0;
}