当前位置： 首页 > news >正文

网络流之最大流(FF, EK, Dinic, SAP)

news 来源：原创 2024/5/20 4:29:46

首先是一些性质：

· 最大流等于最小割

· 平面图的最大流等于其对偶图的最短路(暂时未遇到过题)

· 二分图的最大匹配可通过最大流去求 [对于一个二分图，令已有的边的容量（Capacity）为无穷大，增加一个源点s和一个汇点t，令s和t分别连接二部图中的一个分部，并设置其容量为1。这时得到流网络G，计算得到的最大流就等于最大二分匹配。]


模板以POJ-1273为例，有下面四种方法可以解决。


1.FORD-FULKERSON(FF)

相当于dfs找任意增广路的算法，时间复杂度为 O(V·E^2)，时间效率较低;

#include <algorithm>
#include <iostream>
#include <string.h>
#include <cstdio>
#include <stack>
using namespace std;
const int inf = 0x7fffffff;
const int maxn = 205;
struct node
{
	int v, w, next;
}edge[maxn*maxn];
int no, n, m;
int head[maxn], pre[maxn], rec[maxn], flow[maxn];
stack<int> stk;
void init()
{
	no = 0;
	memset(head, -1, sizeof head);
}
//静态邻接表存边 
void add(int u, int v, int w)
{
	edge[no].v = v; edge[no].w = w;
	edge[no].next = head[u]; head[u] = no++;
	edge[no].v = u; edge[no].w = 0;
	edge[no].next = head[v]; head[v] = no++;
}
int dfs(int S, int T)
{
	memset(pre, -1, sizeof pre);
	while(!stk.empty()) stk.pop();
	pre[S] = S; flow[S] = inf;
	stk.push(S);
	while(!stk.empty())	//用栈迭代替代dfs深搜 
	{
		int top = stk.top(); stk.pop();
		int k = head[top];
		while(k != -1)
		{
			if(pre[edge[k].v] == -1 && edge[k].w > 0)
			{
				flow[edge[k].v] = min(flow[top], edge[k].w);
				pre[edge[k].v] = top;
				rec[edge[k].v] = k;
				stk.push(edge[k].v);
			}
			k = edge[k].next;
		}
		if(pre[T] != -1) return flow[T];
	}
	return -1;
}
int FF(int s, int t)
{
	int ans = 0, add;
	while((add = dfs(s, t)) != -1)	//直到找不到增广路 
	{
		ans += add;
		int k = t;
		while(k != s)
		{
			edge[rec[k]].w -= add;
			edge[rec[k]^1].w += add;
			k = pre[k];
		}
	}
	return ans;
}
int main()
{
	ios::sync_with_stdio(0);
	int u, v, w;
	while(cin >> m >> n) 
	{
		init();
		for(int i = 0; i < m; ++i)
		{
			cin >> u >> v >> w;
			add(u, v, w); 
		}
		cout << FF(1, n) << endl;
	}
	return 0;
}

2.Edmonds-Karp(EK)

相当于用bfs代替dfs找任意增广路的算法，时间复杂度为 O(V·E^2)，时间效率较低;

#include <algorithm>
#include <iostream>
#include <string.h>
#include <cstdio>
#include <queue>
using namespace std;
const int inf = 0x7fffffff;
const int maxn = 205;
struct node
{
	int v, w, next;
}edge[maxn*maxn];
int no, n, m;
int head[maxn], pre[maxn], rec[maxn], flow[maxn];
queue<int> q;
void init()
{
	no = 0;
	memset(head, -1, sizeof head);
}
//静态邻接表存边 
void add(int u, int v, int w)
{
	edge[no].v = v; edge[no].w = w;
	edge[no].next = head[u]; head[u] = no++;
	edge[no].v = u; edge[no].w = 0;
	edge[no].next = head[v]; head[v] = no++;
}
int dfs(int S, int T)
{
	memset(pre, -1, sizeof pre);
	while(!q.empty()) q.pop();
	pre[S] = S; flow[S] = inf;
	q.push(S);
	while(!q.empty())	
	{
		int top = q.front(); q.pop();
		int k = head[top];
		while(k != -1)
		{
			if(pre[edge[k].v] == -1 && edge[k].w > 0)
			{
				flow[edge[k].v] = min(flow[top], edge[k].w);
				pre[edge[k].v] = top;
				rec[edge[k].v] = k;
				q.push(edge[k].v);
			}
			k = edge[k].next;
		}
		if(pre[T] != -1) return flow[T];
	}
	return -1;
}
int EK(int s, int t)
{
	int ans = 0, add;
	while((add = dfs(s, t)) != -1)	//直到找不到增广路 
	{
		ans += add;
		int k = t;
		while(k != s)
		{
			edge[rec[k]].w -= add;
			edge[rec[k]^1].w += add;
			k = pre[k];
		}
	}
	return ans;
}
int main()
{
	ios::sync_with_stdio(0);
	int u, v, w;
	while(cin >> m >> n) 
	{
		init();
		for(int i = 0; i < m; ++i)
		{
			cin >> u >> v >> w;
			add(u, v, w); 
		}
		cout << EK(1, n) << endl;
	}
	return 0;
}

3.Dinic

预处理出层次图，然后再层次图上进行增广，时间复杂度为 O(V^2·E)，时间效率较好;

#include <algorithm>
#include <iostream>
#include <string.h>
#include <cstdio>
#include <queue>
using namespace std;
const int inf = 0x7fffffff;
const int maxn = 205;
struct node
{
	int v, w, next;
}edge[maxn*maxn];
int dis[maxn], pre[maxn], rec[maxn], head[maxn], block[maxn];
int n, m, no;
queue<int> q;
//静态邻接表存边 
inline void add(int u, int v, int w)
{
	edge[no].v = v; edge[no].w = w;
	edge[no].next = head[u]; head[u] = no++;
	edge[no].v = u; edge[no].w = 0;
	edge[no].next = head[v]; head[v] = no++;
}
inline void pre_init()
{
	no = 0;
	memset(head, -1, sizeof head);
}
void init(int S, int T)
{	//初始化一定要注意把所涉及的都覆盖到 
	for(int i = 0; i <= n; ++i)
	{ 
		dis[i] = inf;
		block[i] = 0;	//标记阻塞点 
	} 
	while(!q.empty()) q.pop();
	dis[S] = 0; q.push(S);
	while(!q.empty())	//生成层次图 
	{
		int tp = q.front(); q.pop();
		int k = head[tp];
		while(k != -1)
		{
			if(dis[edge[k].v] == inf && edge[k].w)
			{
				dis[edge[k].v] = dis[tp] + 1;
				q.push(edge[k].v);
			}
			k = edge[k].next;
		}
	}
}
int dinic(int S, int T)
{
	int top = S, ans = 0, flow = inf;
	pre[S] = S; init(S, T);
	while(dis[T] != inf)	//当S无法到达T，不能再增广了 
	{
		int k = head[top];
		while(k != -1)
		{
			if(edge[k].w && dis[edge[k].v] == dis[top]+1 
			&& !block[edge[k].v]) break;
			k = edge[k].next;
		}
		if(k != -1)	//找到下一节点 
		{
			int v = edge[k].v;
			flow = min(flow, edge[k].w);
			pre[v] = top; rec[v] = k;
			top = v;
			if(top == T)
			{
				ans += flow;
				v = -1; k = T;
				while(k != S)
				{
					edge[rec[k]].w -= flow;
					edge[rec[k]^1].w += flow;
					if(!edge[rec[k]].w) v = k;	//寻找距S最近的一个"瓶颈"边 
					k = pre[k];
				}
				flow = inf;	//此处flow必须在外面，大佬的板子可能没注意到，我认为是必须的 
				if(v != -1)	//找到"瓶颈"边 
				{
					top = pre[v];
					k = top;
					while(k != S)
					{
						flow = min(edge[rec[k]].w, flow);
						k = pre[k];
					}
				}
			}
		}
		else
		{
			block[top] = 1;	//找不到下一节点成为阻塞点 
			top = pre[top];	//回溯 
			if(block[S]) init(S, T);//如果S被阻塞，重新计算层次图
			//阻塞点的产生也造成了flow的最小值可能是后面的值，虽然进行一次
			//增广并没什么问题，但上述寻找瓶颈边的判断则是必须的了。 
		}
	}
	return ans;
}
int main()
{
	ios::sync_with_stdio(0);
	int u, v, w;
	while(cin >> m >> n)
	{
		pre_init();
		for(int i = 1; i <= m; ++i)
		{
			cin >> u >> v >> w;
			add(u, v, w);
		}
		cout << dinic(1, n) << endl;
	}
	return 0;
}


/**********************比赛版本***********************/

#include <algorithm>
#include <iostream>
#include <string.h>
#include <cstdio>
#include <queue>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 205;
const int maxm = maxn*maxn;
struct node{int w; int v, next;} edge[maxm];
int pre[maxn], rec[maxn], head[maxn], block[maxn];
int dis[maxn];
int n, m, no;
int S, T;
queue<int> q;
inline void init()
{
	no = 0;
	memset(head, -1, sizeof head);
}
inline void add(int u, int v, int w)
{
	edge[no].v = v; edge[no].w = w;
	edge[no].next = head[u]; head[u] = no++;
	edge[no].v = u; edge[no].w = 0;
	edge[no].next = head[v]; head[v] = no++;
}
void reset(int S, int T)
{
	memset(dis, 0x3f, sizeof dis);
	memset(block, 0, sizeof block);
	q.push(S); dis[S] = 0;
	while(!q.empty())
	{
		int top = q.front(); q.pop();
		for(int k = head[top]; k != -1; k = edge[k].next)
		if(dis[edge[k].v] == inf && edge[k].w)
			dis[edge[k].v] = dis[top]+1, q.push(edge[k].v);
	}
}
int dinic(int S, int T)
{
	int ans = 0, flow = inf;
	int top = S;
	reset(S, T); pre[S] = S;
	while(dis[T] != inf)
	{
		int k, tmp;
		for(k = head[top]; k != -1; k = edge[k].next)
		{
			if(edge[k].w && dis[edge[k].v]==dis[top]+1 && 
			!block[edge[k].v]) break;
		}
		if(k != -1)
		{
			tmp = edge[k].v;
			flow = min(flow, edge[k].w);
			pre[tmp] = top, rec[tmp] = k;
			top = tmp;
			if(top == T)
			{
				ans += flow; tmp = -1;
				for(; top != S; top = pre[top])
				{
					edge[rec[top]].w -= flow;
					edge[rec[top]^1].w += flow;
					if(!edge[rec[top]].w) tmp = top;
				}
				flow = inf;
				if(tmp != -1)
				{
					top = pre[tmp];
					for(; top != S; top = pre[top])
					flow = min(flow, edge[rec[top]].w);
					top = pre[tmp];
				}
			}
		}
		else
		{
			block[top] = 1;
			top = pre[top];
			if(block[S]) reset(S, T);
		}
	}
	return ans;
}
void mapping()
{
	int u, v, w;
	for(int i = 1; i <= m; ++i)
	{
		scanf("%d %d %d", &u, &v, &w);
		add(u, v, w);
	}
}
int main()
{
	while(~scanf("%d %d", &m, &n))
	{
		S = 1, T = n;
		init();
		mapping();
		printf("%d\n", dinic(S, T));
	}
	return 0;
}


4.Shortest Augmenting Paths(SAP)

顾名思义，就是找最短的增广路，把EK算法的O(E)时间优化到了O(V)，故时间复杂度为 O(V^2·E)，加了当前弧优化和间隙优化后的SAP时间效率非常好。

对于Gap优化成立的解释：
假如某次修改d[u]后第一次出现断层k，显然d[u]之前是等于k的，而d[u]修改的原因是修改前d[u] < d[v]+1，所以d[v] > k-1,而因为出现断层k，d[v] != k，故d[v] 〉 k。而由于d函数时单调递增的，所以这个空缺永远不会被填补。而你可能会想会不会存在存在若干个层次k-1的点和层次k+1的点能填补这个空缺？答案是否定的，因为假如存在层次k-1的点和层次k+1的点连边，那么层次k+1的这个点的存在是不合适的，因为不管是初始时候或者是之后修改层次的原因，层次k+1的这个点应该是以层次k存在，而发生断层不存在k层次，所以反证得这个空缺永远填不上。

#include <algorithm>  
#include <iostream>  
#include <string.h>  
#include <cstdio>  
#include <queue>  
using namespace std;  
const int inf = 0x7fffffff;  
const int maxn = 205;  
const int maxm = maxn*maxn; //一定要好好计算边的数量   
struct node  
{  
    int v, w, next;  
}edge[maxm];  
int dis[maxn], pre[maxn], rec[maxn], head[maxn], gap[maxn], now[maxn];  
int n, m, no, up;  //up指逆层次图可能还有增广路时dis的上界 
queue<int> q;  
//静态邻接表存边   
inline void add(int u, int v, int w)  
{  
    edge[no].v = v; edge[no].w = w;  
    edge[no].next = head[u]; head[u] = no++;  
    edge[no].v = u; edge[no].w = 0;  
    edge[no].next = head[v]; head[v] = no++;  
}  
inline void pre_init()  
{  
    no = 0;  up = n;
    memset(head, -1, sizeof head);  
}  
void init(int S, int T)  
{
    for(int i = 0; i <= up; ++i)   
    {
    	now[i] = head[i];   //now用作当前弧的优化   
    	//注意这里now数组要把所有用到的标号都存过来  
    	gap[i] = 0, dis[i] = inf;
    	//初始化一定要注意把所涉及的都覆盖到   
	}
    while(!q.empty()) q.pop();  
    dis[T] = 0; q.push(T);  
    while(!q.empty())   //生成逆层次图   
    {  
        int tp = q.front(); q.pop();  
        ++gap[dis[tp]];  
        int k = head[tp];  
        while(k != -1)  
        {  
            if(dis[edge[k].v] == inf && edge[k^1].w)  
            {  
                dis[edge[k].v] = dis[tp]+1;  
                q.push(edge[k].v);  
            }  
            k = edge[k].next;  
        }  
    }  
}  
int SAP(int S, int T)  
{  
    int ans = 0, flow = inf, top = S;  
    pre[S] = S; init(S, T);  
    while(dis[S] < up)    //当S到T的距离大于等于点的个数时肯定就不能再增广了   
    {                   //切记此处与节点数比较，因为通过方向变会造成距离可能达到节点数  
        if(top == T)  
        {  
            ans += flow;  
            while(top != S) //修改残留网络，并置top为S   
            {  
                edge[rec[top]].w -= flow;  
                edge[rec[top]^1].w += flow;  
                top = pre[top];  
            }  
            flow = inf;  
        }  
        int k = now[top];  
        while(k != -1)  
        {  
            int v = edge[k].v;  
            if(edge[k].w && dis[top] == dis[v]+1)  
            {  
                flow = min(flow, edge[k].w);  
                pre[v] = top; rec[v] = k;  
                now[top] = k;//当前弧的优化   
                top = v;  
                break;  
            }  
            k = edge[k].next;  
        }  
        if(k == -1)  
        {  
            int mind = n;  
            if(--gap[dis[top]] == 0) break;//出现断层，间隙优化   
            int k = now[top] = head[top];//改变当前点的距离标号，也要清除之前的当前弧优化的影响   
            while(k != -1)  
            {  
                if(edge[k].w && mind>dis[edge[k].v]) mind = dis[edge[k].v];  
                k = edge[k].next;  
            }  
            ++gap[dis[top] = mind+1];  
            top = pre[top];//回溯到上一个点   
        }  
    }  
    return ans;  
}
int main()  
{
    ios::sync_with_stdio(0);
	int u, v, w;
	while(cin >> m >> n)
	{
		pre_init();
		for(int i = 1; i <= m; ++i)
		{
			cin >> u >> v >> w;
			add(u, v, w);
		}
		cout << SAP(1, n) << endl;
	}
    return 0;  
}


/**********************比赛版本***********************/

#include <algorithm>  
#include <iostream>  
#include <string.h>  
#include <cstdio>  
#include <queue>  
using namespace std;  
const int inf = 0x3f3f3f3f;  
const int maxn = 205;  
const int maxm = maxn*maxn;
struct node{int w; int v, next;} edge[maxm];  
int pre[maxn], rec[maxn], head[maxn], gap[maxn], now[maxn];  
int dis[maxn];
int n, m, no, up;  
int S, T; 
queue<int> q;
inline void add(int u, int v, int w)  
{  
    edge[no].v = v; edge[no].w = w;  
    edge[no].next = head[u]; head[u] = no++;  
    edge[no].v = u; edge[no].w = 0;  
    edge[no].next = head[v]; head[v] = no++;  
}  
inline void pre_init()  
{  
    no = 0;
    memset(head, -1, sizeof head);  
}  
void init(int S, int T)  
{  
    memset(gap, 0, sizeof gap);  
    memset(dis, 0x3f, sizeof dis);  
    for(int i = 0; i <= up; ++i)   
    now[i] = head[i];
    while(!q.empty()) q.pop();  
    dis[T] = 0; q.push(T);  
    while(!q.empty()) 
    {  
        int tp = q.front(); q.pop();  
        ++gap[dis[tp]];  
        int k = head[tp];  
        while(k != -1)  
        {  
            if(dis[edge[k].v] == inf && edge[k^1].w)  
            {  
                dis[edge[k].v] = dis[tp]+1;  
                q.push(edge[k].v);  
            }  
            k = edge[k].next;  
        }  
    }  
}  
int SAP(int S, int T)  
{
    int ans = 0, flow = inf;
	int top = S;  
    pre[S] = S; init(S, T);  
    while(dis[S] < up)
    {
        if(top == T)  
        {  
            ans += flow;  
            while(top != S)
            {  
                edge[rec[top]].w -= flow;  
                edge[rec[top]^1].w += flow;  
                top = pre[top];  
            }  
            flow = inf;  
        }  
        int k = now[top];  
        while(k != -1)  
        {  
            int v = edge[k].v;  
            if(edge[k].w && dis[top] == dis[v]+1)  
            {  
                flow = min(flow, edge[k].w);  
                pre[v] = top; rec[v] = k;  
                now[top] = k; top = v;  
                break;  
            }  
            k = edge[k].next;  
        }  
        if(k == -1)  
        {  
            int mind = up;  
            if(--gap[dis[top]] == 0) break;
            int k = now[top] = head[top];
            while(k != -1)  
            {  
                if(edge[k].w && mind>dis[edge[k].v]) mind = dis[edge[k].v];  
                k = edge[k].next;  
            }  
            ++gap[dis[top] = mind+1];  
            top = pre[top];  
        }  
    }  
    return ans;  
}  
void mapping()
{
	int u, v, w;
	for(int i = 1; i <= m; ++i)  
    {  
        scanf("%d %d %d", &u, &v, &w); 
        add(u, v, w);  
    }
}
int main()  
{
    while(~scanf("%d %d", &m, &n))  
    {  
		up = n, S = 1, T = n;
        pre_init();  
        mapping();
        printf("%d\n", SAP(S, T)); 
    }  
    return 0;  
}


学习自图论的魅力-网络流。

相关文章：

  • QDU-ycb的ACM进阶之路(多重背包做法)
  • 2017年第0届浙江工业大学之江学院程序设计竞赛决赛—B qwb与矩阵
  • F5 LTM 在SIP消息负载均衡中存在的问题
  • 2017年第0届浙江工业大学之江学院程序设计竞赛决赛—D qwb与神奇的序列
  • 我所爱的世界
  • 2017年第0届浙江工业大学之江学院程序设计竞赛决赛—J qwb又偷懒了
  • 字符串处理文章outline
  • 2017年第0届浙江工业大学之江学院程序设计竞赛决赛—K qwb与小数
  • java内存管理机制
  • 网络流-割的概念以及定理
  • HDU 3533 Escape
  • 容斥原理+模板题HDU-1796
  • Java日志最佳实践
  • 2017年第0届浙江工业大学之江学院程序设计竞赛决赛—A qwb与支教
  • SDUT-3930(线段树+状压)
  • 【347天】每日项目总结系列085（2018.01.18）
  • co.js - 让异步代码同步化
  • CSS 提示工具(Tooltip)
  • ES学习笔记(10)--ES6中的函数和数组补漏
  • fetch 从初识到应用
  • HTML中设置input等文本框为不可操作
  • JS实现简单的MVC模式开发小游戏
  • JS专题之继承
  • niucms就是以城市为分割单位，在上面 小区/乡村/同城论坛+58+团购
  • Node + FFmpeg 实现Canvas动画导出视频
  • oldjun 检测网站的经验
  • springMvc学习笔记（2）
  • zookeeper系列（七）实战分布式命名服务
  • 服务器之间，相同帐号，实现免密钥登录
  • 互联网大裁员：Java程序员失工作，焉知不能进ali？
  • 类orAPI - 收藏集 - 掘金
  • 力扣(LeetCode)22
  • 前嗅ForeSpider教程：创建模板
  • 延迟脚本的方式
  • 一道闭包题引发的思考
  • Redis4.x新特性 -- 萌萌的MEMORY DOCTOR
  • ​如何使用ArcGIS Pro制作渐变河流效果
  • #我与Java虚拟机的故事#连载08：书读百遍其义自见
  • （2）关于RabbitMq 的 Topic Exchange 主题交换机
  • (vue)页面文件上传获取:action地址
  • （八）c52学习之旅-中断实验
  • (附源码)springboot宠物医疗服务网站 毕业设计688413
  • (原)记一次CentOS7 磁盘空间大小异常的解决过程
  • (转)Java socket中关闭IO流后，发生什么事？（以关闭输出流为例） .
  • ***微信公众号支付+微信H5支付+微信扫码支付+小程序支付+APP微信支付解决方案总结...
  • .chm格式文件如何阅读
  • .net 验证控件和javaScript的冲突问题
  • .NET开源快速、强大、免费的电子表格组件
  • /run/containerd/containerd.sock connect: connection refused
  • :如何用SQL脚本保存存储过程返回的结果集
  • @Autowired多个相同类型bean装配问题
  • [CareerCup] 12.3 Test Move Method in a Chess Game 测试象棋游戏中的移动方法
  • [CVPR 2023:3D Gaussian Splatting：实时的神经场渲染]
  • [Flutter]WindowsPlatform上运行遇到的问题总结
  • [ISITDTU 2019]EasyPHP