首页 > 其他分享 >「学习笔记」网络流

「学习笔记」网络流

时间:2023-10-27 17:23:45浏览次数:41  
标签:费用 源点 增广 ll tu 网络 笔记 学习 复杂度

「学习笔记」网络流

点击查看目录

目录

定义部分名词括号内写个英文是为了方便起函数名变量名。

\rvalue/\rvalue/\rvalue/\rvalue/\rvalue/

仅提供大致思路,想看详细点的看上面链接。

建议学的时候自己多手画几个图模拟一下。

常见建模套路,打算以后单开一个博写,因为还有好多套路没有学。

知识点

一些基础定义

主要来自 OI-wiki。

  • 「网络(Flow Network)」:指一张有向图 \(G = (V, E)\)。

  • 「容量(Capacity)」:在一个网络中,对于每一组边 \((u, v) \in E\) 都有一个权值 \(c(u, v)\) 被称为容量。若 \((u, v) \not\in E\) 则 \(c(u, v) = 0\)。

  • 「源点(Source)与汇点(Sink)」:两种存在于网络中的比较特殊的点,所有流从源点 \(s(s\in V)\) 流出,最后流入汇点 \(t(t\in V)\),\(s\neq t\)。

  • 「流(Flow)」:若函数 \(f(u, v)\) 满足以下三点性质:

    1. 容量限制:对于每条边,流经该边的流量不得超过该边的容量,即 \(f(u,v)\leq c(u,v)\)。
    2. 斜对称性:每条边的流量与其相反边的流量之和为 0,即 \(f(u,v)=-f(v,u)\)。
    3. 流守恒性:从源点流出的流量等于汇点流入的流量,即 \(\sum_{(s, u)\in E}f(s,u)=\sum_{(u, t)\in E}f(u,t)\)。

    则 \(f\) 是网络 \(G\) 的流函数。

    对于每一条边 \((u, v)\in E\),\(f(u, v)\) 被称为边 \((u, v)\) 的「流量」,\(c(u, v) - f(u, v)\) 被称为边 \((u, v)\) 的「剩余流量」

    所有流从源点 \(s(s\in V)\) 流出,因此整个网络流量为 \(\sum_{(s, u)\in E}f(s,u)\)。

最大流

  • 「最大流(Max-flow)」:给定一个网络,求一个流函数使这个网络的总流量最大。

Ford-Fulkerson 算法(增广路算法)

  • 「增广路(Augmenting Path)」:一条起点为源点,终点为汇点的剩余流量不为空的边的路径。

这里的增广路与二分图中的不是一个,但是是一个思想。

考虑不断从源点出发寻找增广路并将其跑满,但是这样是错的,因为你增广出来的不一定是最优解里需要的,考虑使这个操作「可撤销」。

解决办法是建立反向边,原来的边流量减多少反向边加多少(流的斜对称性),可以把原来的边上不优的流通过反向边推到另一条边上。

下图是从 OI-wiki 拿的,可以感性理解一下:

image

但是这玩意复杂度保证不了啊!有可能会出现下图这种情况(from rvalue):

graph LR; s-->|23333333|1 1-->|23333333|t 1-->|1|2 2-->|23333333|t s-->|23333333|2

可能会出现流在容量为 \(1\) 的那条边被反复推的情况,这个时候复杂度就取决于值域了。

Edmonds-Karp 算法

简称 EK 算法。

考虑每次找增广路时找最短的增广路。这个直接 01 最短路找,时间复杂度 \(O(E)\)。

不难发现这样找到的增广路长度单调不减,最长为 \(V\),那么考虑迭代次数即可算出时间复杂度。

每次跑增广路都会有一条边流量被跑满,我们称这样的边为「关键边」。每次跑增广路都会出现一条关建边,那么所有边成为「关键边」次数之和即为迭代次数。一条边成为关键边之后暂时会从图中消失,再次出现必须跑其反向边,这时增广路长度必然增加,那么每条边最多 \(V\) 会成为「关键边」,总迭代次数是 \(VE\) 次。

因此总时间复杂度是 \(O(VE^2)\)。

感觉还是不够快,观察发现原因是每次最短的增广路有很多条,但是每次只增广一条。

继续优化。

Dinic 算法

思考如何一次性把所有最短增广路跑了。

按与源点的距离建立分层图,然后跑一遍 DFS 把全图的最短路跑满。

乍一看感觉层数严格递增,DFS 遍历所有点,复杂度是 \(O(VE)\) 的,但是 DFS 中一个点会重复经过所以不能保证其复杂度。

考虑两个优化:

  • 无用点优化
    如果有流量流向一个点的时候这个点流不动了,说明它在当前分层图上不再能做出贡献,可以暂时删去。
  • 当前弧优化
    决定复杂度,不会负优化,你慢了说明你挂了。
    如果当前到点 \(u\) 的流在 \(u\) 遍历完其指向的所有点时用完了,我们记录一下是推向哪条边时用完的,下次再搜索到 \(u\) 时直接从这条边开始推,因为之前的肯定推满了。

考虑计算时间复杂度。

参考 EK 算法时间复杂度的证明,每次找增广路最多找 \(E\) 条,长度最多为 \(V\),分层图层数严格递增,最多会建 \(V\) 次分层图,时间复杂度上限为 \(O(V^2E)\)。

注意到计算复杂度时用词都是「最多」,稍微想一想就会发现不可能跑满,这个复杂度上限是非常松的,一般出题人不会卡你,卡了也没关系,因为这样干就不会有什么人能过题了。

下面是一份实现:

namespace GRAPH {
	class Edge { public: ll v, w, r; };
	class Graph {
	private:
		ll n, s, t, c[N][N];
		std::vector <Edge> tu[N];
	public:
		inline void Init (ll _n, ll _s, ll _t) { 
			n = _n, s = _s, t = _t;
			return;
		}
		inline void AddEdge (ll u, ll v, ll w) {
			c[u][v] += w;
			ll p1 = tu[u].size (), p2 = tu[v].size ();
			tu[u].push_back ((Edge){v, w, p2});
			tu[v].push_back ((Edge){u, 0, p1});
			return;
		}
	private:
		ll dep[N], cur[N];
	public:
		ll maxflow;
	private:
		inline bool DinicBFS () {
			memset (dep, 0, sizeof (dep));
			std::queue <ll> q;
			q.push (s), dep[s] = 1, cur[s] = 0;
			while (!q.empty ()) {
				ll u = q.front (); q.pop ();
				far (p, tu[u]) {
					if (!p.w || dep[p.v]) continue;
					dep[p.v] = dep[u] + 1, cur[p.v] = 0;
					if (p.v == t) return true;
					q.push (p.v);
				}
			}
			return false;
		}
		inline ll DinicDFS (ll u, ll flow) {
			if (u == t || flow <= 0) return flow;
			ll sum = 0, sz = tu[u].size () - 1;
			for (ll &i = cur[u]; i <= sz; ++i) {
				Edge &p = tu[u][i];
				if (!p.w || dep[p.v] != dep[u] + 1) continue;
				ll k = DinicDFS (p.v, std::min (flow, p.w));
				if (k <= 0) dep[p.v] = 0;
				p.w -= k, tu[p.v][p.r].w += k;
				sum += k, flow -= k;
				if (flow <= 0) break;
			}
			return sum;
		}
	public:
		inline void Dinic () {
			maxflow = 0;
			while (DinicBFS ()) maxflow += DinicDFS (s, inf);
			return;
		}
	};
}

最小割

删去一些边,使得 \(s\) 与 \(t\) 不连通,求这些边的最小容量和。

形式化一点:

  • 「割(Cut)」:将网络 \(G\) 分为 \(S\) 和 \(T = V - S\) 两个点集,满足 \(s\in S, t\in T\),则称 \((S, T)\) 为 \(G\) 的一个割。
  • 「割的容量(Cut capacity)」:对于网络 \(G\) 的一个割 \((S, T)\),其容量 \(c(S, T)\) 为 \(\sum_{u \in S, v \in T, (u, v)\in E}c(u, v)\)。
  • 「最小割(Min-cut)」:求一个割 \((S, T)\),使 \(c(S, T)\) 最小。

最大流最小割定理:最大流等于最小割的容量。

稍加思考还是比较好想到证明的。

跑最大流时跑满容量的边全割掉就是一个合法的割了,如果割完后图还联通就说明还有增广路,那就不是最大流了。既然这已经是一种合法的割了那最小割就不可能大于最大流。

如果最小割小于最大流,显然割掉的边是必由之路,应该割掉的边跑满了之后没有增广路了,那就不可能有更多的流流到汇点,假设不成立。

不大于也不小于就只能等于了呗。

费用流

  • 「费用(Cost)」:每条边新增一个权值「费用」,即 \(1\) 单位的流经过这条边所需的费用。单位为 \(a\) 的流经过一条费用和为 \(b\) 的路径所需费用为 \(a\times b\)。
  • 「最小费用最大流(Min-cost max-flow)」:满足流最大的前提下使费用最小。

EK 费用流

仍使用 EK 算法的思路,但是在求最短路的过程,边长度不再是 \(0/1\),而是费用。

注意反向边费用为负,原因考虑反向推流的过程。

ZKW 费用流

Dinic 求分层图换成 SPFA 即可。

但一个比较恶心的事情是,这样不能当前弧优化,无法保证复杂度。

但是上界依然很松,所以随便用!

一份实现:

const ll N = 1e5 + 10, inf = 1ll << 40;

namespace GRAPH {
	class Edge {
	public:
		ll v, w, c, r;
	};
	class Graph {
	private:
		ll n, s, t;
		std::vector <Edge> tu[N];
	public:
		inline void Init (ll _n, ll _s, ll _t) { n = _n, s = _s, t = _t; return; }
		inline void AddEdge (ll u, ll v, ll w, ll c) {
			ll p1 = tu[u].size (), p2 = tu[v].size ();
			tu[u].push_back ((Edge) { v, w, c, p2 });
			tu[v].push_back ((Edge) { u, 0, -c, p1 });
			return;
		}
	private:
		ll dis[N]; bool vis[N];
	public:
		ll maxflow, mincost;
	private:
		inline bool SPFA () {
			memset (vis, 0, sizeof (vis));
			memset (dis, 0x3f, sizeof (dis));
			std::queue <ll> q;
			q.push (s), dis[s] = 0, vis[s] = true;
			while (!q.empty ()) {
				ll u = q.front (); q.pop ();
				far (p, tu[u]) {
					if (!p.w || dis[u] + p.c >= dis[p.v]) continue;
					dis[p.v] = dis[u] + p.c;
					if (!vis[p.v]) q.push (p.v), vis[p.v] = 1;
				}
				vis[u] = false;
			}
			return dis[t] < inf;
		}
		inline ll DFS (ll u, ll flow) {
			if (u == t || flow <= 0) return flow;
			ll sum = 0; vis[u] = true;
			far (&p, tu[u]) {
				if (!p.w || dis[p.v] != dis[u] + p.c || vis[p.v]) continue;
				ll k = DFS (p.v, std::min (flow, p.w));
				sum += k, flow -= k;
				p.w -= k, tu[p.v][p.r].w += k;
				if (flow <= 0) break;
			}
			return sum;
		}
	public:
		inline void Dinic () {
			maxflow = mincost = 0;
			while (SPFA ()) {
				ll f = DFS (s, inf);
				maxflow += f, mincost += f * dis[t];
			}
			return;
		}
	};
}

例题

[SCOI2007] 蜥蜴

拆点后成板子题。

[SDOI2015] 星际战争

二分时间,然后建二分图,在激光武器和巨型机器人之间连容量为无限的边。

源点到激光武器容量为时间乘攻击力,巨型机器人到汇点容量为装甲值。

如果最大流等于总装甲值说明合法。

注意精度问题,建议乘 \(10000\)。

士兵占领

最少很难求,于是转化为每个格都放了士兵之后,最多能去掉多少个士兵。

源点向代表每一行的点连边,容量为这一行最多能删除的士兵数量,列同理。

如果某一个点无障碍,则将其所属行和所属列连边。

[HNOI2007] 紧急疏散EVACUATE

二分时间,然后把一个门拆成多个门,代表不同时间。

然后就比较好想了,但是不好预处理。

[SDOI2009] 晨跑

费用流板子题。

[SDOI2016] 数字配对

比较重要的一个性质是,如果 \(a_i\) 和 \(a_j\) 可以配对,那么两者质因数个数刚好相差一。

那么可以根据质因数个数奇偶性建出二分图然后跑费用流。

[SCOI2007] 修车

发现这个费用很难计算啊。

但是我们有拆点!谁说只能拆成出入点的?

image

你把第 \(i\) 个师傅拆成 \(j\) 个师傅,其中的第 \(k\) 个 \(i\) 号师傅表示这个师傅倒数第 \(k\) 次修车,这个时候花费用的时间要乘 \(k\),因为后面修的 \(k-1\) 车都会被这次耽误。

然后跑一个费用流。

[NOI2012] 美食节

和修车差不多,但是交上去会发现 T 了!怎么回事呢?

点太多了。

你发现一次用不到很多点,所以你考虑动态加点,一个师傅被增广过就给他再拆一个点。

[AHOI2009] 最小割

首先根据证明最大流最小割定理的过程,可行边必须满流。

然后你发现如果残量网络中仍有 \(u\) 到 \(v\) 的路径则 \((u, v)\) 也不是可行边,因为砍了没用。

剩下都是可行边。

然后发现若残量网络 \(S\) 能到 \(u\) 且 \(v\) 能到 \(T\),那么边 \((u, v)\) 是一条必经边。

否则经过这条边的增广路径上还会有与这条边容量一样的边,割掉后效果相同。

考虑跑 Tarjan 后使用 SCC 判定连通。

标签:费用,源点,增广,ll,tu,网络,笔记,学习,复杂度
From: https://www.cnblogs.com/K8He/p/Flow.html

相关文章

  • docker 数据卷-学习
    容器数据卷容器数据存储路径同步在宿主机文件目录做数据持久化保存(目录挂载、映射)不进行这一步,会导致删除容器后,数据直接丢失。容器间数据卷也可以进行共享数据卷的使用,类似于Linux下对目录或文件进行mount1、宿主机目录映射容器内部目录-v宿主机目录:容器内目录(......
  • 第六周学习笔记
    Linux进程管理多任务处理在编程中,多任务处理是指同时执行多个任务或进程的能力。这种能力可以通过并发编程来实现,其中任务可以是同时执行的线程、进程或协程。进程的概念进程:进程是对映像的执行在操作系统内核中,每个进程用一个独特的数据结构表示,叫作进程控制块(PCB)或任务控制......
  • 第七周学习笔记
    并发编程并行计算导论顺序算法与并行算法顺序算法:begin  step_1  step_2  ……  step_nend//nextstep并行算法:cobegin  task_1  task_2  ……  task_ncoend//nextstep并行性与并发性在单CPU系统中,一次只能执行一个任务。不同的任务只能......
  • 按摩学习笔记
    特点按摩,以经络和解剖作为理论基础。具有:经济简便,随时随地,简单有效的特点。能够起到:放松肌肉,舒筋活血,振奋精神,消除病痛等作用。亲身体会以上特点,是我个人经过亲身体会,比较认同的部分。最深刻的体会有:1.个人因为工作经常久坐,导致翻译搜索复制......
  • 《用户故事与敏捷方法》阅读笔记(三)
    用户故事具有多种好处:①用户故事强调口头沟通:自古以来,口头表达是十分重要的。而且相比于书面书写的易产生歧义,口头表述更见简单明了,需求文档也是如此。②人人都可以理解用户故事:相比于一些墨守成规的软件需求里的技术术语,用户故事使用的语言更容易使用户理解,简......
  • docker 网络和iptable的关系
    iptable中四个表的优先级顺序如下:raw:对收到的数据包在连接跟踪前进行处理。一般用不到,可以忽略一旦用户使用了raw表,raw表处理完后,将跳过nat表和ip_conntrack处理,即不再做地址转换和数据包的链接跟踪处理了mangle:用于修改报文、给报文打标签,用得也较少。nat:主要用于做......
  • 【论文解读】RLAIF基于人工智能反馈的强化学习
    【论文解读】RLAIF基于人工智能反馈的强化学习一、简要介绍人类反馈强化学习(RLHF)可以有效地将大型语言模型(LLM)与人类偏好对齐,但收集高质量的人类偏好标签是一个关键瓶颈。论文进行了一场RLHF与来自人工智能反馈的RL的比较(RLAIF)-一种由现成的LLM代替人类标记偏好的......
  • 群签名学习笔记
    群签名算法模型如图所示,群签名包括3个参与主体,群管理、群成员以及验证者。群管理负责群证书的创建管理、群成员管理以及在验证方发起挑战时对成员进行验证追踪群成员加入群后可获得群管理颁发的群证书,并使用证书对某信息进行签名。验证方可验证群签名的合法性。     在群签名......
  • tornado——关于tornado的异步操作学习
    关于tornado的异步操作学习yieldhttp_client.fetch和yieldtornado.gen.Task(http_client.fetch的区别实际上,yieldhttp_client.fetch和yieldtornado.gen.Task(http_client.fetch)是等价的,它们在功能上是相同的。tornado.gen.Task是Tornado4.0版本之前的写法,而yieldh......
  • 易语言银行余额虚拟生成器制作,提供源码思路,仅供学习
    今天这边带来的是一个图片生成器,是用易语言进行开发的,整个代码我算了一下不超过10行,然后就需要一个图片框组件和三个编辑框,三个标签,一个按钮就能实现,真的非常非常简单,大家可以照猫画虎哈,这也仅仅只是为大家做的一个演示示范。软件截图:程序集源码分享:.版本2.程序集窗口程......