prim算法不僅僅可以求最小生成樹，也可以求“最大生成樹”。最小割集Stoer-Wagner算法就是典型的應(yīng)用實(shí)例。
求解最小割集普遍采用Stoer-Wagner算法，不提供此算法證明和代碼，只提供算法思路：
1.min=MAXINT，固定一個(gè)頂點(diǎn)P
2.從點(diǎn)P用類似prim的s算法擴(kuò)展出“最大生成樹”，記錄最后擴(kuò)展的頂點(diǎn)和最后擴(kuò)展的邊
3.計(jì)算最后擴(kuò)展到的頂點(diǎn)的切割值（即與此頂點(diǎn)相連的所有邊權(quán)和），若比min小更新min
4.合并最后擴(kuò)展的那條邊的兩個(gè)端點(diǎn)為一個(gè)頂點(diǎn)（當(dāng)然他們的邊也要合并，這個(gè)好理解吧？）
5.轉(zhuǎn)到2，合并N-1次后結(jié)束
6.min即為所求，輸出min
prim本身復(fù)雜度是O(n^2)，合并n-1次，算法復(fù)雜度即為O(n^3)
如果在prim中加堆優(yōu)化，復(fù)雜度會(huì)降為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表示該點(diǎn)已經(jīng)被刪掉
// 結(jié)點(diǎn)~n
int Stoer_Wagner()
{
int minCut = INT_MAX; // 無向圖最小割
int tmp;
int i, t, j, k, pre;
int s = 1; // 源點(diǎn)
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個(gè)結(jié)點(diǎn)
{
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點(diǎn)
// 合并k點(diǎn)和源點(diǎn)
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());
}
}