网络流建模技巧
这建图,多是一件美事啊!
0.板子
本文中的所有建图思路均参考以下网络流板子实现,如有需要可直接复制。
最大流(使用 Dinic 算法实现):
struct edge {
int cap,flow;
}e[N];
vector <pii> G[N];
int n,m,s,t,tot = -1,dis[N],cur[N];
bool vis[N];
bool BFS() {
memset(dis,0,sizeof dis);
memset(vis,0,sizeof vis);
queue <int> q;
q.push(s);dis[s] = 0;vis[s] = 1;
while (!q.empty()) {
int x = q.front();q.pop();
for (auto ed : G[x]) {
int y = ed.first,num = ed.second;
if (!vis[y] && e[num].cap > e[num].flow) {
vis[y] = 1;
dis[y] = dis[x] + 1;
q.push(y);
}
}
}
return vis[t];
}
int DFS(int x,int res) {
if (x == t || res == 0) return res;
int now = 0;
for (int& i = cur[x];i < G[x].size();++i) {
pii ed = G[x][i];
int y = ed.first,num = ed.second;
if (dis[x] + 1 == dis[y]) {
int f = DFS(y,min(res,e[num].cap - e[num].flow));
if (f > 0) {
e[num].flow += f;
e[num ^ 1].flow -= f;
now += f;
res -= f;
if (!res) break;
}
}
}
return now;
}
int maxflow() {
int ans = 0;
while (BFS()) {
memset(cur,0,sizeof cur);
ans += DFS(s,0x3f3f3f3f);
}
return ans;
}
void addedge(int x,int y,int w) {
G[x].push_back(mp(y,++tot));
e[tot].cap = w;e[tot].flow = 0;
G[y].push_back(mp(x,++tot));
e[tot].cap = 0;e[tot].flow = 0;
}
最小费用最大流(采用 Ford 算法实现):
vector <pii> G[N];
struct edge {
int from,cap,flow,cost;
}e[N];
int tot = -1,s,t;
void addedge(int u,int v,int w,int co) {
e[++tot].cap = w;e[tot].cost = co;e[tot].flow = 0;e[tot].from = u;
G[u].push_back(mp(v,tot));
e[++tot].cap = 0;e[tot].cost = -co;e[tot].flow = 0;e[tot].from = v;
G[v].push_back(mp(u,tot));
}
int dis[N],inq[N],p[N],aaa[N],n,m;
bool Ford(int &flow,int &cost) {
memset(dis,0x3f,sizeof dis);
memset(inq,0,sizeof inq);
queue <int> q;
dis[s] = 0;
inq[s] = 1;
p[s] = 0;aaa[s] = 0x3f3f3f3f;
q.push(s);
while (!q.empty()) {
int x = q.front();q.pop();
inq[x] = 0;
for (auto now : G[x]) {
int y = now.first;
edge& edg = e[now.second];
if (edg.cap > edg.flow && dis[y] > dis[x] + edg.cost) {
dis[y] = dis[x] + edg.cost;
p[y] = now.second;
aaa[y] = min(aaa[x],edg.cap - edg.flow);
if (!inq[y]) {
q.push(y);
inq[y] = 1;
}
}
}
}
if (dis[t] == 0x3f3f3f3f) return 0;
flow += aaa[t];cost += dis[t] * aaa[t];
int x = t;
while (x != s) {
e[p[x]].flow += aaa[t];
e[p[x] ^ 1].flow -= aaa[t];
x = e[p[x]].from;
}
return 1;
}
pii MCMF() {
int cost = 0,flow = 0;
while (Ford(flow,cost));
return mp(flow,cost);
}
匈牙利算法:
int n,m,e,ans,match[N];
bool vis[N];
vector <int> G[N];
bool dfs(int x) {
for (auto y : G[x]) {
if (!vis[y]) {
vis[y] = 1;
if (!match[y] || dfs(match[y])) {
match[y] = x;
match[x] = y;
return 1;
}
}
}
return 0;
}
int Hungary() {
int ans = 0;
for (int i = 1;i <= n;++i) {
memset(vis,0,sizeof vis);
if (dfs(i)) ++ans;
}
return ans;
}
1.基本建图
最简单的一类建图,通常就是题目给的边你把它按照要求建出来就好,就是纯考察板子的了。
例题:
一共有
n 个飞行员,其中有m 个外籍飞行员和(n - m) 个英国飞行员,外籍飞行员从1 到m 编号,英国飞行员从m + 1 到n 编号。 对于给定的外籍飞行员与英国飞行员的配合情况,试设计一个算法找出最佳飞行员配对方案,使皇家空军一次能派出最多的飞机。
n,m \leq 100
没啥好说的,直接按照题目的给定要求飞行员建边即可。但是注意如果用 Dinic 返回路径可能不是很好写(其实也没多难),所以可以用匈牙利来实现。
2.最小割
在网络流里很重要的一个东西就是最小割,个人想先提一下这个东西以便于接下来的一些技巧的讲解。
首先引用一下 OI-wiki 里的定义:
割
对于一个网络流图
G=(V,E) ,其割的定义为一种 点的划分方式:将所有的点划分为S 和T=V-S 两个集合,其中源点s\in S ,汇点t\in T 。割的容量
我们的定义割
(S,T) 的容量c(S,T) 表示所有从S 到T 的边的容量之和,即c(S,T)=\sum_{u\in S,v\in T}c(u,v) 。当然我们也可以用c(s,t) 表示c(S,T) 。最小割
最小割就是求得一个割
(S,T) 使得割的容量c(S,T) 最小。
用这张图来理解,下图中灰色的点就是属于
我们一般结合 最大流最小割定理 来对其相关问题进行求解。
定理:
f(s,t)_{\max} = c(s,t)_{\min} 证明:考虑
u\in S,v \in T ,(u, v) 一定满流,否则残余网络中存在(u, v) ,v 能被源点到达。考虑
u \in S, v \in T,(v, u) \in E ,(u, v) 一定没有流,否则残余网络中存在(u, v) ,v 能被源点到达。那么
\sum _{u∈S,v∈T} (f(u, v) − f(v, u)) = \sum_{u∈S,v∈T} c(u, v) ,即流量等于这个割的容量,且这个流是最大流。这说明:不存在增广路的时候,流就是最大流。而最大流的时候,不存在增广路。
所以一个流是最大流当且仅当残余网络不存在增广路。同时这也给出了求最小割可行方案的方法。
用人话来说,想象一下如果一个流没有跑满的话,那么必定还有边是有剩余容量,那么就还可以流过去,也就是说没被割掉,
最小割建图一般用在我们称作 二者选其一 的模型,一般如下:
有
n 个物品和两个集合A,B ,如果将一个物品放入A 集合会花费a_i ,放入B 集合会花费b_i ;还有若干个形如u_i,v_i,w_i 限制条件,表示如果u_i 和v_i 同时不在一个集合会花费w_i 。每个物品必须且只能属于一个集合,求最小的代价。
首先我们建立源点与汇点
如果把
有时候我们在建图时,为了满足一些需求会连边权为无穷大的边,这里的边权就代表一种选择方案,不影响最小割(因为无穷大不可能在最小割方案中)但是提供了一种路径。
所以直接最大流即可。
例题 1:
小 M 在 MC 里开辟了两块巨大的耕地
A 和B (你可以认为容量是无穷),现在,小 P 有n 种作物的种子,每种作物的种子有1 个(就是可以种一棵作物),编号为1 到n 。现在,第
i 种作物种植在A中种植可以获得a_i 的收益,在B 中种植可以获得b_i 的收益,而且,现在还有这么一种神奇的现象,就是某些作物共同种在一块耕地中可以获得额外的收益,小 M 找到了规则中共有m 种作物组合,第i 个组合中的作物共同种在A 中可以获得c_{1,i} 的额外收益,共同种在B 中可以获得c_{2,i} 的额外收益。小 M 很快的算出了种植的最大收益,但是他想要考考你,你能回答他这个问题么?
n \leq 10^3
就和上面讲的东西一样了,是板子题。但是注意这个组合的关系实际上是不太好处理的,所以可以额外建
例题 2:
给定一个
n \times n 的矩阵B 和一个1 \times n 的矩阵C 。求出一个1×n 的 01 矩阵A ,使得D=(A×B-C)×A^{\sf T} 最大,其中A^{\sf T} 为A 的转置,输出D 。
直接看课件吧,写的很清楚了(
3.拆点
一般来说,对于拆点我们一个点都会有多个点,但是对于同一张图我们在编号的处理上为了避免错乱,本文推荐大家写一个类似如下的函数返回每个点在每个状态的编号,可以极大减少 Debug 工作量。
int gethash(int x,int y,int typ) {
return typ * n * m + (x - 1) * m + y;
}
//Example
addedge(gethash(x,y,0),gethash(x,y,1),cap);
基础拆点
这部分拆点适用于一类给了你点权,却没有给边权的很讨厌的问题。
通常我们把这个点拆成一个入点和一个出点,在入点和出点间连容量为点权的边。
对于一条边
以及有些题目会要求你去割点而不是割边,那么这样的题目我们把原本的
例题:
John 的奶牛们喜欢通过电邮保持联系,于是她们建立了一个奶牛电脑网络,以便互相交流。这些机器用如下的方式发送电邮:如果存在一个由
c 台电脑组成的序列a_1,a_2,\cdots ,a_c ,且a_1 与a_2 相连,a_2 与a_3 相连,等等。那么电脑a_1 和a_c 就可以互发电邮。很不幸,有时候奶牛会不小心踩到电脑上,农夫约翰的车也可能碾过电脑,这台倒霉的电脑就会坏掉。这意味着这台电脑不能再发送电邮了,于是与这台电脑相关的连接也就不可用了。
有两头奶牛就想:如果我们两个不能互发电邮,至少需要坏掉多少台电脑呢?请编写一个程序为她们计算这个最小值。
这个题就是刚才说的方法了,注意是双向边,所以要建两次。
按照约束拆点
这部分拆点适用于一类给了你每个点在某个状态,并且这个状态不是很大的时候的问题。
结合例题来讲吧。
现有
n 个太空站位于地球与月球之间,且有m 艘公共交通太空船在其间来回穿梭。每个太空站可容纳无限多的人,而太空船的容量是有限的,第i 艘太空船只可容纳h_i 个人。每艘太空船将周期性地停靠一系列的太空站,例如(1,3,4) 表示该太空船将周期性地停靠太空站134134134\dots 。每一艘太空船从一个太空站驶往任一太空站耗时均为1 。人们只能在太空船停靠太空站(或月球、地球)时上、下船。初始时所有人全在地球上,太空船全在初始站。试设计一个算法,找出让所有人尽快地全部转移到月球上的运输方案。
1 \leq n \leq 13,1 \leq m \leq 20,1 \leq k \leq 50 。
这题的建图就要按时间来考虑了,很明显的一点是,要把每一天都连向汇点然后求出总和。这个时候我们发现,如果其他的点仅仅只是一个点的话,无法满足求出每一天这个要求,因为会互相影响,这个时候我们就相应的把这些点拆成天数这么多个点,然后分别向向对应的天数连边。
源点向每一个星球一条容量为无穷大的边,每个空间站向下一时间的该空间站连一条容量为无穷大的边,代表时间间的转移。
每个飞船现在在哪个星球,下一秒会飞到哪一个星球都可以计算得到,所以直接连边,容量为飞船载人量。
然后就做完了,记得判断月球和地球是否联通即可。
4.二维类建图
这类建图有一种比较典型的套路。
染色连边
这种题的套路一般是让你在一个二维数组中选择一些元素,并且这些元素选择之间有一定的限制。通常连边方法就是把
例题1:
有一个
m 行n 列的方格图,每个方格中都有一个正整数。现要从方格中取数,使任意两个数所在方格没有公共边,且取出的数的总和最大,请求出最大的和。
n,m \leq 100
这题就是类似上边的方法,这里直接给出连边的代码。
s = n * m + 1,t = n * m + 2;
for (int i = 1;i <= n;++i) {
for (int j = 1;j <= m;++j) {
read(a[i][j]);ans += a[i][j];
if ((i + j) & 1) addedge(s,gethash(i,j),a[i][j]);
else addedge(gethash(i,j),t,a[i][j]);
}
}
for (int i = 1;i <= n;++i) {
for (int j = 1;j <= m;++j) {
for (int nxt = 0;nxt < 4;++nxt) {
int nx = i + dx[nxt],ny = j + dy[nxt];
if ((((nx + ny) & 1) == 0 && ((i + j) & 1) == 1)
&& nx <= n && ny <= m && nx > 0 && ny > 0) {
addedge(gethash(i,j),gethash(nx,ny),0x3f3f3f3f);
}
}
}
}
例题2:
经过千辛万苦小 A 得到了一块切糕,切糕的形状是长方体,小 A 打算拦腰将切糕切成两半分给小 B。出于美观考虑,小 A 希望切面能尽量光滑且和谐。于是她找到你,希望你能帮她找出最好的切割方案。
出于简便考虑,我们将切糕视作一个长
P 、宽Q 、高R 的长方体点阵。我们将位于第z 层中第x 行、第y 列上的点称(x,y,z) ,它有一个非负的不和谐值v(x,y,z) 。一个合法的切面满足以下两个条件:
与每个纵轴(一共有
P\times Q 个纵轴)有且仅有一个交点。即切面是一个函数f(x,y) ,对于所有(x,y)(x\in [1,P],y\in[1,Q]) ,我们需指定一个切割点f(x,y) ,且1\le f(x,y)\le R 。- 切面需要满足一定的光滑性要求,即相邻纵轴上的切割点不能相距太远。对于所有的
1\le x,x_1;\le P 和1\le y,y_1;\le Q ,若|x-x_1;|+|y-y_1|=1 ,则|f(x,y)-f(x_1,y_1)| \le D ,其中D 是给定的一个非负整数。可能有许多切面
f 满足上面的条件,小 A 希望找出总的切割点上的不和谐值最小的那个。P,Q,R \leq 40
首先按照套路,先把每个
这题也是按照黑白染色的套路进行连边,对于光滑性的要求,我们不难发现从
5.二分图
二分图似乎没有很必要介绍?节点由两个集合组成,且两个集合内部没有边的图。
接下来给出一些相关定理,有些较简单不给出证明。
最大匹配
将源点连上左边所有点,右边所有点连上汇点,容量皆为 1。原来的每条边从左往右连边,容量也皆为 1,最大流即最大匹配。
最小覆盖数
所有顶点中选择最少的顶点来覆盖所有的边。
最大独立集
选最多的点,满足两两之间没有边相连。
二分图中,最大独立集 =
证明:首先我们可以看出除了我们选择的两个用来最小覆盖的点之外,剩下的点之间彼此之间都没有连边,我们可以尝试把任意两个红点之间连一条边,那么明显,我们不满足最小覆盖的要求了,或者我们尝试通过转换使最小覆盖更小。当然不可行,因为我们已经求得就是最小覆盖了,并且易证的是剩下的所有点一定构成一个独立集。并且这个独立集的大小不能够更大了,然后我们就证出了题目所给的定理。
例题
在一个
n \times n 个方格的国际象棋棋盘上,马(骑士)可以攻击的棋盘方格如图所示。棋盘上某些方格设置了障碍,骑士不得进入。对于给定的
n \times n 个方格的国际象棋棋盘和障碍标志,计算棋盘上最多可以放置多少个骑士,使得它们彼此互不攻击。
1 \leq n \leq 200 ,0 \leq m \lt n^2
首先先按照上面二维建图的套路,黑白染色拆点,发现这个题实际上就让我们求这个二分图的最大独立集。
这种有冲突关系的套路都是把冲突关系当成边来建,然后求独立集,注意这题 ban 掉的点不能选,建边的时候避开这些点就行。
DAG 最小路径覆盖
首先拆点,对于点
答案就是原图的节点数 - 最大匹配。
证明的话感性理解下:一开始一共有
6.一些常用特殊性质图模型
最大权闭合子图
定义:闭合图一般指一个图中点的集合,从该集合中所有的点出发,能到达的点要求都必须在该点集中。
也就是说,从该集合中出发,一定要回到该集合中,不能出到集合外。通俗理解就是集合之间的点有关联性(可以类比有向图里的 DAG)。
最大权闭合子图,顾名思义,就是所有闭合子图中点权之和最大的那个,注意这里的权指的是点权,因为闭合图是对于点集而言的。
关于求解,可以直接套最小割的模型进行解决,源点向所有点权为正的点连容量为点权的边,所有点权为负的点连容量向汇点连为点权绝对值的边。然后求最小割,再用所有点权为正的权值之和减去最小割,就是我们要求的最大权值和了。
证明:
如何从最大权闭合子图转化到最小割的呢?首先我们要知道简单割的定义,简单割指的是割集的所有边都是从
s 出发的边或终点是t 的边。由此,我们知道在上述建图方式中的最小割一定是一个简单割,因为其图内部的边的流量是正无穷,所以最小割集一定不包含内部的边,是一个简单割。
然后我们需要证明闭合子图和简单割是一一对应的,从而我们求闭合子图的最值就是简单割的最小值,也就是建的新图的最小割。
我们假设一个闭合子图是
V ,流网络分成两个集合S 和T ,构成一个割集的情况。S 包含的是V + s (闭合子图的点+源点);T 包含的是剩下的所有点(闭合子图外的点+汇点)。在这种情况下闭合子图
V 就和这个割[S,T] 相对应,且这个割是个简单割。这样我们就将闭合子图问题转化成了割的问题了,然后我们就要看看数量关系,找到最大权闭合子图和最小割间的数量表达式,就可以借助最小割模型计算最大权闭合子图了。 首先我们要找到最小割的计算表达式,下面是割集的所有情况:
我们将原图中的点分为两个集合,
V_1 和V_2 ,V_1 是闭合子图的点集,V_2 是原图中剩下的所有点,割集就只剩两种情况s 到V_2 和V_1 到T ,根据建图方式可得:前者的容量和是V_2 中所有点权为正的和,后者容量和是V_1 中所有点权为负数的和的相反数,割集的容量之和就是V_2 中所有点权为正的和+ V_1 中所有点权为负数的和的相反数。然后我们再看我们要求的闭合子图权值之和的计算表达式:最大权值和就等于
V_1 中所有的权值和,即V_1 中所有点权为正的和 +V_1 中所有点权为负的和。我们将上面求出来的两个表达式相加可得:割集容量之和+闭合子图权值之和=原图中所有点权为正数的点权之和(后面的相加后刚好抵消)。而等式的右边是个定值,我们为使闭合子图权值最大化,所以我们就要使得割集容量之和最小化,即求最小割的大小,再用所有点权为正的权值之和减去最小割,就是我们要求的最大权值了。
一般这种模型就适合投入
例题:
在前期市场调查和站址勘测之后,公司得到了一共
N 个可以作为通讯信号中转站的地址,而由于这些地址的地理位置差异,在不同的地方建造通讯中转站需要投入的成本也是不一样的,所幸在前期调查之后这些都是已知数据:建立第i 个通讯中转站需要的成本为P_i (1 \leq i \leq N )。另外公司调查得出了所有期望中的用户群,一共
M 个。关于第i 个用户群的信息概括为A_i ,B_i 和C_i :这些用户会使用中转站A_i 和中转站B_i 进行通讯,公司可以获益C_i 。(1 \leq i \leq M ,1 \leq A_i ,B_i \leq N )THU 集团的 CS&T 公司可以有选择的建立一些中转站(投入成本),为一些用户提供服务并获得收益(获益之和)。那么如何选择最终建立的中转站才能让公司的净获利最大呢?(净获利 = 获益之和 – 投入成本之和)
N \leq 5000,M \leq 5\times 10^4
这个题把用户群当成权值为正的点,把中转站当成权值为负的点,如上建图即可。注意源点一定要连到权值为正的,不要搞反了。
结语
推荐练习
以上就是网络流建图的基本思想了,接下来可以进行更多的练习。个人推荐以下题单:
参考
最详细(也可能现在不是了)网络流建模基础 - ~victorique~
感谢以上内容提供方。
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可。
色
啊对对对