最小割
求无向图的最小割
最小割集◎Stoer-Wagner算法
一个无向连通网络，去掉一个边集可以使其变成两个连通分量则这个边集就是割集；最小割集当然就权和最小的割集。
可以用最小切割最大流定理：
1.min=MAXINT,确定一个源点
2.枚举汇点
3.计算最大流，并确定当前源汇的最小割集，若比min小更新min
4.转到2直到枚举完毕
5.min即为所求输出min
不难看出复杂度很高：枚举汇点要O(n)，最短增广路最大流算法求最大流是O((n^2)m)复杂度，在复杂网络中O(m)=O(n^2)，算法总复杂度就是O(n^5)；哪怕采用最高标号预进流算法求最大流O((n^2)(m^0.5))，算法总复杂度也要O(n^4)
所以用网络流算法求解最小割集复杂度不会低于O(n^4)。
－－－－－－－－－
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
using namespace std;
int mat[600][600];
int res;
//Stoer-Wagner算法，加了自己看得懂的备注
//无向图全局最小割，用求prim类似方法o（n^3)，学习了一个下午……
//一开始用枚举源点汇点的最大流求解，复杂度o(n^5) 超时
void Mincut(int n) {
int node[600], dist[600];
bool visit[600];
int i, prev, maxj, j, k;
for (i = 0; i < n; i++)
node[i] = i;
while (n > 1) {
int maxj = 1;
for (i = 1; i < n; i++) { //初始化到已圈集合的割大小
dist[node[i]] = mat[node[0]][node[i]];
if (dist[node[i]] > dist[node[maxj]])
maxj = i;
}
prev = 0;
memset(visit, false, sizeof (visit));
visit[node[0]] = true;
for (i = 1; i < n; i++) {
if (i == n - 1) { //只剩最后一个没加入集合的点，更新最小割
res = min(res, dist[node[maxj]]);
for (k = 0; k < n; k++) //合并最后一个点以及推出它的集合中的点
mat[node[k]][node[prev]] = (mat[node[prev]][node[k]] += mat[node[k]][node[maxj]]);
node[maxj] = node[--n]; //缩点后的图
}
visit[node[maxj]] = true;
prev = maxj;
maxj = -1;
for (j = 1; j < n; j++)
if (!visit[node[j]]) { //将上次求的maxj加入集合，合并与它相邻的边到割集
dist[node[j]] += mat[node[prev]][node[j]];
if (maxj == -1 || dist[node[maxj]] < dist[node[j]])
maxj = j;
}
}
}
return;
}
int main() {
int n, m, a, b, v;
while (scanf("%d%d", &n, &m) != EOF) {
res = (1 << 29);
memset(mat, 0, sizeof (mat));
while (m--) {
scanf("%d%d%d", &a, &b, &v);
mat[a][b] += v;
mat[b][a] += v;
}
Mincut(n);
printf("%d\n", res);
}
}
本文来自CSDN博客，转载请标明出处：https://www.sodocs.net/doc/c112171109.html,/michael200892458/archive/2009/11/22/4850931.aspx
poj 2914 minimum cut 无向图全局最小割_光之龙的空间_
求无向图的最小割算法
居然比普通的最小割的复杂度还低
stoer-wagner 算法用来求无向图 g=(v, e)的全局最小割。
算法基于这样一个定理：对于任意s, t v ∈ ，全局最小割或者等于原图的s-t 最小割，或者等于将原图进行 contract(s,
t)操作所得的图的全局最小割。
算法框架：
1. 设当前找到的最小割mincut 为+∞
2. 在 g中求出任意 s-t 最小割 c，mincut = min(mincut, c)
3. 对 g作 contract(s, t)操作，得到 g'=(v', e')，若|v'| > 1，则g=g'并转 2，否则mincut 为原图的全局最
小割
contract 操作定义：
若不存在边(p, q)，则定义边(p, q)权值w(p, q) = 0
contract(a, b): 删掉点 a, b 及边(a, b)，加入新节点 c，对于任意v v ∈ ，w(v, c) = w(c, v) = w(a, v) + w(b,
v)
求 g=(v, e)中任意 s-t 最小割的算法：
定义w(a, x) = ∑w(v[i], x)，v[i] a ∈
定义 ax 为在x 前加入 a 的所有点的集合（不包括 x）
1. 令集合 a={a}，a为 v中任意点
2. 选取 v - a中的 w(a, x)最大的点 x加入集合 a
3. 若|a|=|v|，结束
令倒数第二个加入 a的点为 s，最后一个加入 a的点为 t，则s-t 最小割为
w(at, t)
#include
using namespace std;
const int maxn=510;
int map[maxn][maxn];
int n;
void contract(int x,int y)
{
int i,j;
for (i=0;i if (i!=x) map[x][i]+=map[y][i],map[i][x]+=map[i][y]; for (i=y+1;i { map[i-1][j]=map[i][j]; map[j][i-1]=map[j][i]; } n--; } int w[maxn],c[maxn]; int sx,tx; int mincut() { int i,j,k,t; memset(c,0,sizeof(c)); c[0]=1; for (i=0;i for (i=1;i+1 { t=k=-1; for (j=0;j k=w[t=j]; c[sx=t]=1; for (j=0;j } for (i=0;i } int main() { #ifdef _debug freopen("in.in","r",stdin); #endif int i,j,k,m; while (scanf("%d%d",&n,&m)!=eof) { memset(map,0,sizeof(map)); while (m--) { scanf("%d%d%d",&i,&j,&k); map[i][j]+=k; map[j][i]+=k; } int mint=999999999; while (n>1) { k=mincut(); if (k contract(sx,tx); } printf("%d\n",mint); } return 0; } https://www.sodocs.net/doc/c112171109.html,/s/blog_6af663940100n532.html 【转】最小割的一点理解 (2010-10-29 16:12:28) 转载 分类：【Sweep---图论】 标签： 最小割 杂谈 转自mjmjmtl大牛： 一、基本问题： 1.到底什么是割：原始点集为V，选出一些点集S使得s∈S，T=V-S，t∈T，则S到T的边为S到T割，记做[S,T]。 2.什么是最小割：图中所有的割中，边权值和最小的割为最小割！ 3.割得容量容量和流量计算的区别：割[S,T]的容量为∑(边(u,v)的容量和)，其中u∈S,∈T。也就是说割的容量不计算反向的边！！而流量为正向的和反向的代数和。 4.最大流-最小割定理：最大流的值为最小割的容量！ 5.怎样求割：求完最大流后，在残留网络中从source开始dfs，被染色的为S，未被染色的为T，则边集[S,T]为割。（或者从sink反向dfs，被染色的为T，未被染色的为S，边集[S,T]为割）这种思想应该没有错误，我曾经证明过，正向和反向floodFill都能得到合适的解。然而我按照逆向floodFill提交了两道special judge的题，都没有AC！分别是spoj839和poj2125（其中poj2125的SPJ有问题，一会AC一会WA），然而，对于spoj839我自己对我的逆向floodFill答案和正向floodFill答案做了对比(如果有区别，在程序中会死循环)，发现二者没有区别。感觉是SPJ的问题。这一点，暂且放置，以后再次看到了再说。 二、一些割的性质： 1.割[S,T]，流量只能从S流向T，不能从T流向S！（在最大流后找割dfs时其实就满足这个性质，假设T中一个点v流向S中的一个点u，那么u到v有负流量，则u到v的残留网络严格大于0。反向dfs证明类似） 2.最大流后，割边一定满流。减小某一割边后，网络流减小。 3.如下图，从s沿着残余流量dfs，得到点集S；同理沿着t反向dfs，得到点集T；剩下的是M。分界线cut1和cut2是其中一割，边自然为割边。然而在M中还存有割边（一定存有！！否则M就没用了！） 4.退化一下：如下图所示，S和T有相邻部分边集E1，S和M重合边集相邻部分边集E2，M和T相邻边集部分E3，那么直接升高E1中某条边的容量，会使整体容量直接增高！反之：而如果增大S和M相邻的割边或者M和T相邻的割边，网络流不直接增大，因为M 中还存有割边限制 5.继续退化：如果M==空集，cut1和cut2重合（变为cut），则网络中割唯一。可以通过if ( |S|+|T|==总点数) 来判断 三、割的三个典型应用（参考《最小割模型在信息学竞赛中的应用》）：最大权闭合图、最大密度子图、二分图的最小点权覆盖（二分图的最大点权独立集） https://www.sodocs.net/doc/c112171109.html,/view/986baf00b52acfc789ebc9a9.html 第八章 图与网络分析 也叫网络规划。我们讲三个问题：最短路问题，最大流问题，最小费用最大流问题。 第一讲： 最短路问题（与上章设备更新凑成一讲） 最短路问题是网络理论中应用最广泛的问题之一。许多优化问题都可以使用这个模型，如设备更新、管道的铺设、线路的安排、厂区的布局等。 最短路问题的一般提法是：设),(E V G =为连通图，图中各边),(j i v v 有权ij l （ij l =∞表示i v ，j v 之间没有边），s v ，t v 为图中任意两点，求一条道路μ，使它是从s v 到t v 的所有路中总权最小的路。即：)(μL = ∑∈ μ),(j i v v ij l 。 最短路算法中1959年由Dijkstra （狄克斯特洛）提出的算法被公认为是目前最好的方法，我们称之为Dijkstra 算法。下面通过例子来说明此法的基本思想。 条件：所有的权数ij l ≥0。 思路：逐步探寻。 下求1v 到8v 的最短路： 1） 从1v 出发，向8v 走。首先，1v 到1v 的距离为0，给1v 标号（0）。画第一个圈。（表 明已标号，或已走出1v ） 2） 从1v 出发，只有两条路可走，（1v ，2v ），（1v ，3v ），其距离记为11k ，12k 。当然 想选一条长度短的路，即 Min ｛（12k ）,13k ｝=｛4,6｝=4 给2v 标号（4）：表明走出1v 后走向8v 的最短路目前看是2v ，最优距离是4。 ○1给（1v ，2 v ）划成粗线。 1v （08（15） ○ 2划第二个圈。 现已完成第二个圈内的路已考察完毕，或者说，已走出包含1v ，2v 的第二个圈。 3）出了第二个圈，接着往下走，有三条路可走：（1v ，3v ），（2v ，4v ），（2v ，5v ）。那条路最近？记三条路长度为13k ，24k ，25k ，即求： Min ｛（13k ）,24k ,25k ｝=min ｛6,9,8｝=6 给3v 标号（6）：表明从第二个圈出来最近的一站是3v ，总长度是6。 ○1给（1v ，3v ）划成粗线。 ○ 2划第三个圈。 表明：圈内的点已完成考察。 4）现已走出第三个圈，向8v 奔。有四条路可走，最优路线在何方？即： Min ｛24k ,（25k ）,34k ,35k ｝=min ｛9,8,10,13｝=8 给5v 标号（8）：表明从第三个圈出来后最近的一站是5v ，总长度是8。 ○1给（2v ，5v ）划成粗线。 ○ 2划第四个圈。 表明：圈内的点已完成考察。 5）现已走出第四个圈，向8v 奔。有四条路可走，最优路线在何方？即： Min ｛56k ,57k ,（24k ）,34k ｝=min ｛13,14,9,10｝=9 给4v 标号（9）：表明从第四个圈出来后最近的一站是4v ，总长度是9。 ○1给（2v ，4v ）划成粗线。 ○ 2划第五个圈。 表明：圈内的点已完成考察。 6）现已走出第五个圈，向8v 奔。有四条路可走，最优路线在何方？即： Min ｛46k ,47k ,（56k ）,57k ｝=min ｛18,16,13,14｝=13 给6v 标号（13）：表明从第五个圈出来后最近的一站是6v ，总长度是13。 ○1给（5v ，6v ）划成粗线。 ○ 2划第六个圈。 最大流和最小割的最短增益路径法 实验目的： 1.理解迭代改进基本原理； 2.掌握最短增益路径法； 实验平台： Microsoft Visual C++ 6.0 实验过程： 1.编程实现最短增益路径算法： #include *Pre, //标记流向,正为前向,负为后向 *Sign, //顶点是否标记,0为未标记,1为已标记 *P; //过程变量,记录流量bool SignN(); //标记顶点 int Min(int a,int b); //计算最小值 void Update(); //更新网络 }; G::G() {Pre=NULL;} G::G(int n,int start,int end) { N=n; Start=start; End=end; Map=new int*[N+1]; Flow=new int*[N+1]; Rest=new int*[N+1]; Pre=new int[N+1]; Sign=new int[N+1]; P=new int[N+1]; for(int i=1;i<=N;i++) { Map[i]=new int[N+1]; Flow[i]=new int[N+1]; Rest[i]=new int[N+1]; Sign[i]=0; P[i]=0; 中图分类号： O157.6 本科生毕业论文（设计） （申请学士学位） 论文题目最大流问题 作者姓名蔡凌捷 专业名称信息与计算科学 指导教师王龙芹 2011年6月04日 学号：2007211416 论文答辩日期：2011年6月04日指导教师： 滁州学院本科毕业设计（论文）原创性声明 本人郑重声明：所呈交的设计（论文）是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果。本人完全意识到本声明的法律后果由本人承担。 作者签名： 2011年05月30日 目录 摘要 (1) Abstract (1) 1. 研究背景与基本概念 (2) 1.1基本概念 (3) 1.2相关应用 (8) 2. 最大流问题 (9) 2.1 主要浏览线路的游客容量测算 (9) 2.2 转化成网络图、求最大流 (10) 3. 结果与分析 (12) 参考文献 (13) 致谢 (14) 最大流问题 摘要：本文对最大流问题的基本概念及其相关应用进行了研究。其中着重对最大流的相关应用展开研究。在最大流定理的研究应用中，选择了旅游景点中的游客流量问题，以及改造道路方案上如何最有效地达到最大流。在实际问题解决上，通过相关旅游资料，分析了旅游景点环境的测算数据；通过数学图论中网络最大流问题构造了数学模型。探索旅游景点道路改造时，找到使其景点的整个道路网络达到最大流通量最为有效的方法。 关键词：最大流；有向图；流量；网络 中图分类号：O157.6 The Problem of Max-flow Abstract:This paper studies the basic concept of the maximun flow problem and its associated applications. One focuses on the maximum flow launched research related applications. In the research and application of flow theory, chose tourist flow problem in the tourist attractions, and how to transform road scheme most effectively to achieve maximum flow. In the practical problem solving, through the relevant travel material, analyzes the environmental measuring data of tourist attraction; using network maximum flow in the mathematical graph theory to construct the mathematical model. As exploring remodeling tourist attractions road, find out the most effective way to reach the maximum flow of the whole road network . Key words: Max-flow; Digraph; V alue of a flow; Network最大流最小割
最大流和最小割的最短增益路径法
最大流最小割论文