prim算法不僅僅可以求最小生成樹，也可以求“最大生成樹”。最小割集Stoer-Wagner算法就是典型的應用實例。
求解最小割集普遍采用Stoer-Wagner算法，不提供此算法證明和代碼，只提供算法思路：
1.min=MAXINT，固定一個頂點P
2.從點P用類似prim的s算法擴展出“最大生成樹”，記錄最后擴展的頂點和最后擴展的邊
3.計算最后擴展到的頂點的切割值（即與此頂點相連的所有邊權和），若比min小更新min
4.合并最后擴展的那條邊的兩個端點為一個頂點（當然他們的邊也要合并，這個好理解吧？）
5.轉到2，合并N-1次后結束
6.min即為所求，輸出min
prim本身復雜度是O(n^2)，合并n-1次，算法復雜度即為O(n^3)
如果在prim中加堆優化，復雜度會降為O((n^2)logn)
#include <cmath>
#include <cstdio>
#include <memory.h>
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <vector>
#include <string>
#include <queue>
using namespace std;
const int N = 500 + 3;
int n, m;
int mat[N][N];
int dist[N];
int visited[N];
int del[N]; // true表示該點已經被刪掉
// 結點~n
int Stoer_Wagner()
{
int minCut = INT_MAX; // 無向圖最小割
int tmp;
int i, t, j, k, pre;
int s = 1; // 源點
memset(del, 0, sizeof(del));
for (t = 1; t < n; t++) // n - 1次Maximum Adjacency Search
{
for (i = 1; i <= n; i++)
if (!del[i])
dist[i] = mat[s][i];
memset(visited, 0, sizeof(visited));
visited[s] = 1;
k = s;
for (i = 1; i <= n - t; i++) // 每次剩下n - t + 1個結點
{
tmp = -1e9;
pre = k;
k = 0;
for (j = 1; j <= n; j++)
{
if (!del[j] && !visited[j] && dist[j] > tmp)
{
k = j;
tmp = dist[j];
}
}
if (!k) return 0; // 不連通
visited[k] = 1;
for (j = 1; j <= n; j++)
if (!del[j] && !visited[j])
dist[j] += mat[k][j];
}
minCut = min(minCut, dist[k]);
del[k] = 1; // 刪除k點
// 合并k點和源點
for (i = 1; i <= n; i++)
if (!del[i] && i != pre)
{
mat[pre][i] += mat[k][i];
mat[i][pre] = mat[pre][i];
}
}
return minCut;
}
int main ()
{
int u, v, w, i;
while (scanf("%d%d", &n, &m) != EOF)
{
memset(mat, 0, sizeof(mat));
while (m--)
{
scanf("%d%d%d", &u, &v, &w);
if (u == v) continue;
mat[u + 1][v + 1] += w;
mat[v + 1][u + 1] += w;
}
printf("%d\n", Stoer_Wagner());
}
}