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());
}
}