设计师专用网站,网站 内容建设存在的问题,郑州网站策划,怎么设计门户网站网络流总结 基础知识最大流最小割定理 最大流EKdinic模型二分图匹配无源汇上下界可行流有源汇上下界最大、最小流多源汇最大流最大流之关键边最大流之拆点最大流建图实战 最小割模型最大权闭合子图最大密度子图最小点权覆盖集最大点权独立集最小割建图实战 费用流EK模型费用流与… 网络流总结 基础知识最大流最小割定理 最大流EKdinic模型二分图匹配无源汇上下界可行流有源汇上下界最大、最小流多源汇最大流最大流之关键边最大流之拆点最大流建图实战 最小割模型最大权闭合子图最大密度子图最小点权覆盖集最大点权独立集最小割建图实战 费用流EK模型费用流与上下界最大流结合费用流建图实战 最小割树 基础知识 \qquad 流网络是一个有源点 s s s 和汇点 t t t 的有向图不考虑反向边记为 G ( V , E ) G(V,E) G(V,E)。其中每一条边都有一个容量 c ( u , v ) c(u,v) c(u,v) 和一个流量 f ( u , v ) f(u,v) f(u,v)。对于该网络中的一个流 f f f如果其满足两个条件1、容量限制即每条边都满足 0 ≤ f ( u , v ) ≤ c ( u , v ) 0\leq f(u,v)\leq c(u,v) 0≤f(u,v)≤c(u,v)2、流量守恒即除去源点汇点以外每个点 x x x 都满足 ∑ u ∈ V f ( u , x ) ∑ v ∈ V f ( x , v ) \sum_{u\in V}f(u,x)\sum_{v\in V}f(x,v) ∑u∈Vf(u,x)∑v∈Vf(x,v)那么我们称流 f f f 是流网络 G G G 的一个可行流。可行流的流量 ∣ f ∣ ∑ u ∈ V f ( s , u ) − ∑ v ∈ V f ( v , s ) |f|\sum_{u\in V}f(s,u)-\sum_{v\in V}f(v,s) ∣f∣∑u∈Vf(s,u)−∑v∈Vf(v,s)即从源点流出的流量减去流入源点的流量。 \qquad 残留网络是针对于原图中的一个流来说的。即我们只能说“流 f f f 的残留网络 G f G_f Gf”。残留网络对于原图中的每一条边都增加一条反向边这条反向边的流量与原图中边的流量相等。可以将残留网络中的边理解为“退流”。 \qquad 两个可行流是可以相加减的叠加的方式就是每条边上的流量对应相加减而且得到的结果也一定是原图的一个可行流。 \qquad 如果一个流网络中存在一条路径这条路径中的任意一条边都没有达到满流即 f ( u , v ) c ( u , v ) f(u,v)c(u,v) f(u,v)c(u,v)那么我们称这条路径为一条增广路径。 \qquad 流网络中的最大流指的是最大可行流即第一要满足此流是一条可行流其次要满足它的流量是本图所有可行流中最大的一个。 \qquad 流网络中的割指的是将图中的所有点分为 S , T S,T S,T 两个点集记作 C ( S , T ) C(S,T) C(S,T)。这两个点集要满足1、 s ∈ S , t ∈ T s\in S,t\in T s∈S,t∈T2、 S ∩ T ∅ S\cap T\emptyset S∩T∅3、 S ∪ T V S\cup TV S∪TV。割的容量定义为 ∑ u ∈ S , v ∈ T c ( u , v ) \sum_{u\in S,v\in T}c(u,v) ∑u∈S,v∈Tc(u,v)割的流量定义为 ∑ u ∈ S , v ∈ T f ( u , v ) − ∑ u ∈ T , v ∈ S f ( u , v ) \sum_{u\in S,v\in T}f(u,v)-\sum_{u\in T,v\in S}f(u,v) ∑u∈S,v∈Tf(u,v)−∑u∈T,v∈Sf(u,v)。流网络中的最小割指的是容量最小。
最大流最小割定理 \qquad 最大流最小割定理包含三条内容这三条内容知一推二分别是1、可行流 f f f 是最大流2、可行流 f f f 的残留网络中不存在增广路3、存在某个割 C ( S , T ) C(S,T) C(S,T)满足 ∣ f ∣ C ( S , T ) |f| C(S,T) ∣f∣C(S,T)。
最大流 \qquad 求最大流有两种算法 E K EK EK 和 d i n i c dinic dinic。
EK \qquad 根据最大流最小割定理我们可以得知当残留网络中不存在增广路时该残留网络对应的流 f f f 一定是最大流。 E K EK EK 算法便是基于这个原理每次 b f s bfs bfs 找残留网络中的增广路并将其增广直到网络中不存在增广路为止。 \qquad E K EK EK 算法时间复杂度为 O ( n m 2 ) O(nm^2) O(nm2)不过网络流算法记时间复杂度用处不大。思路很简单实现也很容易。
const int maxn 110;
const int maxm 5010;
typedef long long LL;
int n, m, S, T;
struct pic {int to, lst;LL cap;
}edge[maxm 1];
int head[maxn], tot -1/*边从0开始编号目的是方便成对变换*/, pre[maxn]/*记录每个点第一次被搜到的前驱边是哪一条*/;
queue int q;
LL d[maxn];//记录到达当前点时当前增广路径的最大流量inline void add(int x, int y, int z) {edge[ tot] {y, head[x], 1LL * z};head[x] tot;
}bool bfs() {//寻找增广路memset(vis, 0, sizeof vis);while(!q.empty()) q.pop();q.push(S), vis[S] 1, d[S] 1e9 7;while(!q.empty()) {int x q.front(); q.pop();for(int i head[x]; ~i; i edge[i].lst) {int y edge[i].to;if(!vis[y] edge[i].cap/*有流量时才有意义去搜*/) {d[y] min(d[x], edge[i].cap);//更新最大流量vis[y] 1, pre[y] i;if(y T) return 1;//找到了一条增广路q.push(y);}}}return 0;
}LL EK() {LL ans 0;while(bfs()) {ans d[T];for(int x T; x ! S; x edge[pre[x] ^ 1/*成对变换*/].to) edge[pre[x]].cap - d[T], edge[pre[x] ^ 1].cap d[T];//对增广路进行增广操作}return ans;
}
//main中
memset(head, -1, sizeof head);
scanf(%d%d%d%d, n, m, S, T);
for(int i 1, x, y, z; i m; i ) {scanf(%d%d%d, x, y, z);add(x, y, z), add(y, x, 0)/*建残留网络一开始流量都是0*/;
}
printf(%lld\n, EK());
}dinic \qquad 在 E K EK EK 的基础之上我们考虑优化。 \qquad E K EK EK 每次 b f s bfs bfs 只找出来了一条增广路进行增广效率较低。 d i n i c dinic dinic 算法依据分层思想每次找出多条增广路同时进行增广而且还有三处小优化总体时间复杂度 O ( n 2 m ) O(n^2m) O(n2m)不过法律规定网络流不许卡 dinic。
bool bfs() {//找增广路memset(d, -1, sizeof d);//分层while(!q.empty()) q.pop();d[1] 0/*源点层数为0*/, q.push(1), cur[1] head[1];//当前弧优化while(!q.empty()) {int x q.front(); q.pop();for(int i head[x]; ~i; i edge[i].lst) {int v edge[i].to; LL w edge[i].cap;if(d[v] -1 w) {d[v] d[x] 1/*记录点v在点x下一层*/, cur[v] head[v];//记录从哪一条边开始跑if(v n) return 1;q.push(v);}}}return 0;
}LL Find(int x, LL limit) {//limit:当前增广路径的最大流量if(x n) return limit;//到了汇点LL flow 0;//增广了多少流量for(int i cur[x]; ~i flow limit/*优化1最重要当flowlimit再搜下去就无意义了因为无法继续增广了*/; i edge[i].lst) {cur[x] i;//优化2当前弧优化int v edge[i].to; LL w edge[i].cap;if(d[v] d[x] 1/*判断点v是否是点x的下一层*/ w) {LL t Find(v, min(w, limit - flow));if(!t) d[v] -1;//优化3如果这个点往后的流量是0说明通过此点无法进行增广直接删除即可edge[i].cap - t, edge[i ^ 1].cap t, flow t;}}return flow;
}LL dinic() {LL flow 0, ans 0;while(bfs()) while(flow Find(1, INF)) ans flow;return ans;
}模型
二分图匹配 \qquad 例题飞行员配对方案问题圆桌问题。 \qquad 套路用最大流中边的容量来对边进行限制。
无源汇上下界可行流 \qquad 问题给定一个包含 n n n 个点 m m m 条边的有向图每条边都有一个流量下界和流量上界。求一种可行方案使得在所有点满足流量平衡条件的前提下所有边满足流量限制。 \qquad 对于上下界的限制形式化写出来是 c l o w ( u , v ) ≤ f ( u , v ) ≤ c u p ( u , v ) c_{low}(u,v)\leq f(u,v)\leq c_{up}(u,v) clow(u,v)≤f(u,v)≤cup(u,v)我们可以选择让不等式同时减去 c l o w ( u , v ) c_{low}(u,v) clow(u,v) 从而变成只有上界的问题。但是减完之后可能会有点不满足流量守恒此时我们需要建立超级源点、超级汇点根据每个点是少流还是多流来对它们进行补偿或减少即与源点连还是与汇点连。而且为了保证这些点一定流量守恒与源点、汇点相连的边必须要是满流的。所以我们连好与超级源点、汇点的边后直接在新网络上跑最大流如果跑出来的不是满流那么原问题一定无解否则让新网络中每条边的流量加上原来的下界就是原问题的一个可行流。 \qquad 核心 C o d e Code Code
for(int i 1, a, b, c, d; i m; i ) {scanf(%d%d%d%d, a, b, c, d);add(a, b, d - c/*减去下节*/, c/*同时储存下界*/), add(b, a, 0, 0);A[a] - c, A[b] c;//记录每条边减去下界后每个点流量的变化
}
int all 0;
for(int i 1; i n; i ) {if(A[i] 0) add(S, i, A[i], 0), add(i, S, 0, 0), all A[i];//少流了需要补else if(A[i] 0) add(i, T, -A[i], 0), add(T, i, 0, 0);//多留了需要放
}
if(dinic() all) puts(NO);//不满流无解
else {puts(YES);for(int i 1; i (m 1); i 2) printf(%d\n, edge[i].cap edge[i ^ 1].lower);//加上下界
}有源汇上下界最大、最小流 \qquad 面对上下界我们可以考虑建一条从汇点指向源点容量为 I N F INF INF 的边这样就转化为了无源汇上下界问题。我们可以先沿用无源汇上下界可行流的算法跑出一个可行流然后将新添的边删去再从源点向汇点跑出一个最大流将这两个流相加便是答案。证明我也不太会…… \qquad 核心 C o d e Code Code
for(int i 1, a, b, c, d; i m; i ) {scanf(%d%d%d%d, a, b, c, d);add(a, b, d - c), add(b, a, 0);A[a] - c, A[b] c;
}
int all 0;
for(int i 1; i n; i ) {if(A[i] 0) add(S, i, A[i]), add(i, S, 0), all A[i];else if(A[i] 0) add(i, T, -A[i]), add(T, i, 0);
}
add(t, s, INF), add(s, t, 0);//添加一条t-sINF的边
if(dinic() all) puts(No Solution);
else {int res edge[tot].cap;//跑出来的可行流注意不是dinic返回的流因为dinic返回的是S到T的我们需要的是s到t的edge[tot].cap edge[tot ^ 1].cap 0, S s, T t;printf(%d\n, res dinic());
}\qquad 对于最小流我们让上述代码输出 r e s − d i n i c ( ) res-dinic() res−dinic() 即可。证明我还是不会……
多源汇最大流 \qquad 超级源点指向各个源点各个汇点指向超级汇点然后跑最大流即可。
最大流之关键边 \qquad 问题如果升高一条边的容量可以使得最大流变大那么我们称这条边为“关键边”。现在求网络中有几条“关键边”。 \qquad 我们思考什么样的边可以成为关键边 \qquad 在跑完最大流后如果存在一条路径这条路径中只有一条边是满流的那么这条边一定是关键边。证明也很显然。那么我们只需跑完最大流后分别从源点和汇点开始 d f s dfs dfs每次只走没满流的边。搜完之后如果一条边的两端点分别被源点和汇点搜到那么它一定是关键边。
最大流之拆点 \qquad 当我们有时要对点进行限制时我们可以考虑拆点在拆出的点之间加边来满足对点的限制。 \qquad 例题[USACO07OPEN] Dining G最长不下降子序列问题。
最大流建图实战 \qquad 例题MPIGS - Sell Pigs[SCOI2007] 蜥蜴清理雪道。
最小割 \qquad 根据“最大流最小割定理”我们可以得知网络中最小割的容量就是最大流的流量所以我们完全可以用求最大流的方法求最小割。 \qquad 但是如果让求最小割的方案怎么办呢 \qquad 参考最大流求关键边的做法我们可以从源点开始 d f s dfs dfs每次只走没满流的边。最后如果有一条边的两个端点有一个被搜到了另一个没有那么这条边就要被割开。这也就意味着整个图可以被分为“被搜到的点”和“没被搜到的点”两个点集。这样其中一个合法方案就求出来了。
模型
最大权闭合子图 \qquad 对于图 G ( V , E ) G(V,E) G(V,E)如果它的一个子图 G ′ ( V ′ , E ′ ) G(V,E) G′(V′,E′) 满足 V ′ V V′ 中的任意一个点的任意一条出边都在 E ′ E E′ 内那么就称 G ′ G G′ 是 G G G 的一个闭合子图。如果给每个点附上点权可为负那么点权最大的一个闭合子图称为最大权闭合子图。 \qquad 如果给出一个带点权的图我们怎么求解它的最大权闭合子图呢 \qquad 首先我们分别建立超级源点、超级汇点超级源点指向所有正点权的点边权为这个点的点权所有负点权的点指向超级汇点边权为这个点点权的绝对值对于原图中的边正常建在网络上边权为 I N F INF INF。此时我们设所有正点权的点的点权和为 r r r。建好图之后在图上跑一个最小割设这个最小割的权值是 s s s那么原图的最大权闭合子图的权值便是 r − s r-s r−s。 \qquad 例题[NOI2006] 最大获利太空飞行计划问题[NOI2009] 植物大战僵尸。
最大密度子图 \qquad 我们定义一个图 G ( V , E ) G(V,E) G(V,E) 的密度为 ∣ E ∣ ∣ V ∣ \frac{|E|}{|V|} ∣V∣∣E∣最大密度子图指的便是图 G G G 中使得 ∣ E ′ ∣ ∣ V ′ ∣ \frac{|E|}{|V|} ∣V′∣∣E′∣ 最大的子图 G ′ ( V ′ , E ′ ) G(V,E) G′(V′,E′)。 \qquad 既然是要让一个分式最大那么就一定要用到 0 / 1 0/1 0/1 分数规划。设当前二分的值为 g g g那么我们就要尽可能找到 ∣ E ′ ∣ − g ∣ V ′ ∣ |E|-g|V| ∣E′∣−g∣V′∣ 的最大值。在求最大值的过程中我们可以借助最小割来推导式子并求解。 \qquad 核心 C o d e Code Code
bool check(db x) {memset(head, -1, sizeof head), tot -1;for(int i 1; i m; i ) add(E[i].first, E[i].second, 1), add(E[i].second, E[i].first, 1);for(int i 1; i n; i ) add(S, i, m), add(i, S, m), add(i, T, 1.0 * m 2 * x - du[i]), add(T, i, 1.0 * m 2 * x - du[i]);//m:赋的一个偏移量return 1.0 * m * n - dinic() 0.0;
}最小点权覆盖集 \qquad 问题给定一张有向图我们现在需要覆盖这张有向图中的所有边。对于一个点 i i i我们可以花费 W i W_i^ Wi 的代价覆盖所有指向它的边花费 W i − W_i^- Wi− 的代价覆盖所有它指出的边问最小需要花费多少代价 \qquad 对于这种有向图问题我们可以考虑拆点套路将一个点拆成 i i i 和 i n in in 两个点。如果是无向图那就直接连边即可。然后我们建立超级源点从超级源点引一条容量为 W i W_i^ Wi 的边指向点 i i i再建立超级汇点从 i n in in 引一条容量为 W i − W_i^- Wi− 的边指向超级汇点。对于原图中的一条有向边 ( x , y ) (x,y) (x,y)我们引一条从 x x x 指向 y n yn yn容量为 I N F INF INF 的边。此时我们跑出的最小割便是最小代价。 \qquad 跑完之后我们遍历从源点指出的边。如果源点指向 v v v 的边满流了就说明我们要选择 W u W_u^ Wu最后我们遍历一遍所有边如果边 ( x , y ) (x,y) (x,y) 此时没有选 W y W_y^ Wy那么我们就要选择 W x − W_x^- Wx−。这样我们就得到了一组合法方案。
最大点权独立集 \qquad 问题给定一张图每个点有点权我们需要选出一些点使得这些点在没有边相连的基础上点权和最大。 \qquad 根据经典结论最大权独立总-最小权覆盖所以我们还按照上一种类型建边跑出最小覆盖后用总点权减去最小覆盖即可。
最小割建图实战 \qquad 例题CABLETV - Cable TV Network骑士共存问题文理分科。
费用流 \qquad 费用流全称为“最小费用最大流”或“最大费用最大流”它是建立在最大流的基础之上的。费用流问题中每条边不仅有容量还有一个费用 w w w表示每流过单位流量就会产生 w w w 的费用。费用流的算法基础是最大流的 E K EK EK只不过把中间 b f s bfs bfs 的过程改为了 s p f a spfa spfa 求最短路即最小花费。
EK \qquad 大体跟最大流的 E K EK EK 很像只是改了 b f s bfs bfs 为 s p f a spfa spfa还是很好理解的。 \qquad 核心 C o d e : Code: Code:
inline void add(int a, int b, int c, int d) {edge[ tot] {b, head[a], c, d}, head[a] tot;edge[ tot] {a, head[b], 0, -d}, head[b] tot;//注意残留网络中边的费用是-d
}bool spfa() {memset(incf, 0, sizeof incf), memset(dis, 0x7f, sizeof dis);//incf:最大流量 dis:最小费用dis[S] 0, incf[S] INF, q.push(S), vis[S] 1;while(!q.empty()) {int x q.front(); q.pop(), vis[x] 0;for(int i head[x]; ~i; i edge[i].lst) {int To edge[i].to, Val edge[i].val, Cost edge[i].cost;if(Val dis[To] dis[x] Cost) {dis[To] dis[x] Cost;incf[To] min(incf[x], Val);pre[To] i;if(!vis[To]) q.push(To), vis[To] 1;}}}return incf[T] 0;//判断能否跑到汇点
}void EK(int flow, int cost) {
[添加链接描述](https://www.luogu.com.cn/problem/P4015) while(spfa()) {flow incf[T], cost incf[T] * dis[T];//flow:最大流 cost:最小费用for(int i T; i ! S; i edge[pre[i] ^ 1].to) edge[pre[i]].val - incf[T], edge[pre[i] ^ 1].val incf[T];}return ;
}模型 \qquad 费用流的题目较好写主要有一类是费用流与上下界最大流的结合。
费用流与上下界最大流结合 \qquad 例题[NOI2008]志愿者招募。 \qquad 带上下界我们仍旧采取减去下界的方式转化。但是本题还有一个最主要的问题在于一个志愿者工作的是一段区间是“一对多”这是正常建边无法做到的。遇到这种情况我们可以考虑从区间终点向区间起点连一条边转化为无源汇可行流来做即可。
费用流建图实战 \qquad 例题餐巾计划问题运输问题负载平衡问题分配问题深海机器人问题数字梯形问题K取方格数。
最小割树 \qquad 最小割树上任意两点路径上边权最小值为这两点的最小割权值。 \qquad 模板核心 C o d e Code Code
void build(int l, int r) {if(l r) return ;S id[l], T id[r];Add(id[l], id[r], dinic());int tmps1 0, tmps2 0;for(int i l; i r; i ) {if(d[id[i]] ! -1) tmp1[ tmps1] id[i];else tmp2[ tmps2] id[i];}for(int i l; i l tmps1 - 1; i ) id[i] tmp1[i - l 1];for(int i l tmps1; i r; i ) id[i] tmp2[i - (l tmps1) 1];build(l, l tmps1 - 1), build(l tmps1, r);
}\qquad 例题最小割树模板[CQOI2016] 不同的最小割[ZJOI2011]最小割Pumping Stations。
