首页 > 代码库 > POJ2914 （未解决）无向图最小割|Stoer-Wagner算法|模板
POJ2914 （未解决）无向图最小割|Stoer-Wagner算法|模板
还不是很懂，贴两篇学习的博客：
http://www.hankcs.com/program/algorithm/poj-2914-minimum-cut.html
http://blog.sina.com.cn/s/blog_700906660100v7vb.html
算法步骤：
1. 设最小割cut=INF, 任选一个点s到集合A中, 定义W(A, p)为A中的所有点到A外一点p的权总和.
2. 对刚才选定的s, 更新W(A,p)(该值递增).
3. 选出A外一点p, 且W(A,p)最大的作为新的s, 若A!=G(V), 则继续2.
4. 把最后进入A的两点记为s和t, 用W(A,t)更新cut.
5. 合并st，即新建顶点u, 边权w(u, v)=w(s, v)+w(t, v), 删除顶点s和t, 以及与它们相连的边.
6. 若|V|!=1则继续1.
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 7 #define MAX_N 500 + 16 8 #define INF 0x3f3f3f3f 9 10 int G[MAX_N][MAX_N];11 int v[MAX_N]; // v[i]代表节点i合并到的顶点12 int w[MAX_N]; // 定义w(A,x) = ∑w(v[i],x)，v[i]∈A13 bool visited[MAX_N]; // 用来标记是否该点加入了A集合14 15 int stoer_wagner(int n)16 {17 int min_cut = INF;18 for (int i = 0; i < n; ++i)19 {20 v[i] = i; // 初始还未合并，都代表节点本身21 }22 23 while (n > 1)24 {25 int pre = 0; // pre用来表示之前加入A集合的点（在t之前一个加进去的点）26 memset(visited, 0, sizeof(visited));27 memset(w, 0, sizeof(w));28 for (int i = 1; i < n; ++i)29 {30 int k = -1;31 for (int j = 1; j < n; ++j) // 选取V-A中的w(A,x)最大的点x加入集合32 {33 if (!visited[v[j]])34 {35 w[v[j]] += G[v[pre]][v[j]];36 if (k == -1 || w[v[k]] < w[v[j]])37 {38 k = j;39 }40 }41 }42 43 visited[v[k]] = true; // 标记该点x已经加入A集合44 if (i == n - 1) // 若|A|=|V|（所有点都加入了A），结束45 {46 const int s = v[pre], t = v[k]; // 令倒数第二个加入A的点（v[pre]）为s，最后一个加入A的点（v[k]）为t47 min_cut = min(min_cut, w[t]); // 则s-t最小割为w(A,t)，用其更新min_cut48 for (int j = 0; j < n; ++j) // Contract(s, t)49 {50 G[s][v[j]] += G[v[j]][t];51 G[v[j]][s] += G[v[j]][t];52 }53 v[k] = v[--n]; // 删除最后一个点（即删除t，也即将t合并到s）54 }55 // else 继续56 pre = k;57 }58 }59 return min_cut;60 }61 62 int main(int argc, char *argv[])63 {64 int n, m;65 while (scanf("%d%d", &n, &m) != EOF)66 {67 memset(G, 0, sizeof(G));68 while (m--)69 {70 int u, v, w;71 scanf("%d%d%d", &u, &v, &w);72 G[u][v] += w;73 G[v][u] += w;74 }75 printf("%d\n", stoer_wagner(n));76 }77 return 0;78 }
POJ2914 （未解决）无向图最小割|Stoer-Wagner算法|模板
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。