無(wú)向圖全局最小割。Stoer_Wagner算法。只會(huì)用，具體證明還沒(méi)弄懂，我這代碼很挫啊，跑了9秒。
#include <stdio.h>
#include <string.h>
#define N 505
#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 src = 1;
memset(del, 0, sizeof(del));
for(int i = 1; i < n; i++) //n - 1次合并
{
for(int j = 1; j <= n; j++)
if(!del[j])
{
w[j] = g[src][j];
}
memset(visit, 0, sizeof(visit));
visit[src] = 1;
int mmin, cur = src, pre;
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 n, m, ans;
while(~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);
if(a == b) continue;
a++, b++;
g[a][b] += c;
g[b][a] += c;
}
ans = Stoer_Wagner(n);
printf("%d\n", ans);
}
return 0;
}