【模板】网络流相关

模板】网络流相关"/>

【模板】网络流相关

网络流相关模板

网络流是 acm 竞赛中的一种题型，一般流程是：建出图论模型，之后直接使用板子跑最大流、费用流等。

通常有着数据范围小、建模较难看出的特点，需要做题人有一定经验。同时，这种题目对代码能力的要求，则仅限于板子。

本文中将举出作者的一些板子，阅读需要有一定的网络流基础，如有不对的地方也欢迎大家斧正。

---

1. 最大流

最大流毫无疑问是网络流基础中的基础。本文给出的板子使用的是最为常用的 dinic 算法。

dinic 兼具书写快捷、好理解、实际运行效率优的特点，主要思想是使用 bfs 在残量网络上建立分层图，在分层图上找到所有增广路。

代码如下：

#include <iostream>
#include <limits>
#include <array>
#include <queue>using namespace std;
const int maxn = 300, maxm = 200000; // 点数、边数的上限
typedef long long LL;
const int inf = numeric_limits<int>::max();
class netFlow{struct edge{ // 网络流中的边类int to;int flow; // 代表当前剩余流量int nxt;edge(int to=0, int flow=0, int nxt=0):to(to), flow(flow), nxt(nxt){}} e[maxm];
public:int S, T;void addEdge(int x, int y, int f) // 向网络流中加边{e[++totEdge] = edge(y, f, head[x]);head[x] = totEdge;e[++totEdge] = edge(x, 0, head[y]); // 如果是无向边，可以直接把这里的流量写作fhead[y] = totEdge;return;}bool bfs(int st) // bfs 分层{queue <int> q;q.push(st);level.fill(0);level[st] = 1;while(q.empty()==false){int k=q.front();q.pop();for(int i=head[k]; i; i=e[i].nxt){int v=e[i].to;if(!level[v] && e[i].flow){level[v] = level[k]+1;q.push(v);}}}return !!level[T];}int dfs(int u, int flow) // dfs 寻找增广路{if(u==T || !flow) return flow;int ret=0;for(int i=head[u]; i; i=e[i].nxt){int v=e[i].to;if(e[i].flow && level[v] == level[u] + 1){int now=dfs(v, min(flow, e[i].flow));if(now){ret+=now;flow-=now;e[i].flow-=now;e[i^1].flow+=now;if(!flow) return ret;}else level[v] = 0;}}return ret;}int solve() // 求解网络最大流{int result=0;while(bfs(S)){result += dfs(S, inf);}return result;}void clear() // 网络流清空{S = T = 0;totEdge=1;head.fill(0);return;}
private:int totEdge=1; // 第一条边从 2 开始，方便使用 i^1 定位反向边array <int, maxn > head;array <int, maxn > level;
};

此外，还有诸如 当前弧优化 ，ISAP算法，预流推进 等优化或者算法，如有卡常需要可以使用。

---

2.最小费用最大流

最小费用最大流 简称 费用流，是满足最大流量的基础上，最小化费用。

注意最小费用最大流处理的问题中，费用是对于单位流量计算的。

代码如下：

#include <iostream>
#include <array>
#include <limits>
#include <queue>using namespace std;
typedef long long LL;
typedef pair <LL, LL > pll;
const int maxm = 1000001, maxn = 300001;
const LL inf = numeric_limits<LL>::max();
class netflow{struct edge{int to;LL flow; // 流量LL cost; // 单位流量费用int nxt;edge(int to=0, LL flow=0, LL cost=0, int nxt=0):to(to), flow(flow), cost(cost), nxt(nxt){}}e[maxm];
public:int S, T;void addEdge(int x, int y, LL f, LL c){e[++totEdge] = edge(y, f, c, head[x]);head[x] = totEdge;e[++totEdge] = edge(x, 0, -c, head[y]);head[y] = totEdge;return;}pll solve();
private:int totEdge=1;array < int, maxn > head, pre;array < LL, maxn > flow, dist;array < bool ,maxn > inqueue;bool SPFA(int st);
};
bool netflow::SPFA(int st){ // 使用 SPFA 寻找路径queue <int> q;flow.fill(inf);dist.fill(inf);q.push(st);dist[st] = 0;inqueue[st] = true;pre[T] = 0;while(q.empty()==false){int k = q.front();q.pop();inqueue[k]=false;for(int i=head[k]; i; i=e[i].nxt){int v=e[i].to;if(e[i].flow && dist[v]>dist[k]+e[i].cost){dist[v] = dist[k]+e[i].cost;flow[v] = min(flow[k], e[i].flow);pre[v] = i; // pre 记录每个点由哪条边转移而来if(!inqueue[v])inqueue[v] = true, q.push(v);}}}return !!pre[T];
}
pll netflow::solve() // 求解费用流
{LL maxflow = 0, mincost = 0;while(SPFA(S)){maxflow += flow[T];mincost += flow[T]*dist[T];int x = T;while(x != S){ // 增广e[pre[x]].flow -= flow[T];e[pre[x]^1].flow += flow[T];x=e[pre[x]^1].to;}}return make_pair(maxflow, mincost);
}

本文给出的代码使用的是 SPFA 算法寻找增广路。鉴于 SPFA 已经好卡到了人人喊打的程度，费用流诞生了 基于 Dijkstra 增广 的算法（更准确说是 Johnson算法）。

此外对于一些结构、性质特殊的图，可以不建出网络流跑费用流，这种黑科技称为 模拟费用流 。

---

3. 无源汇上下界可行流

也称为 环流问题，给出网络中每条边的流量的上下界，求是否存在一种环流满足：(1) 每条边的流量在上下界限制之内； (2) 每个点流量平衡。

思路是让每条边先跑满下界，然后考察每个点的盈亏情况。

先说做法：

记 f ( p ) f(p) f(p) 表示某一结点 p p p 的 流入量 − - − 流出量。

如果 f ( p ) > 0 f(p) > 0 f(p)>0，则 连边 S → p S\rightarrow p S→p 流量为 f ( p ) f(p) f(p) ；

如果 f ( p ) < 0 f(p) < 0 f(p)<0，则 连边 p → T p\rightarrow T p→T 流量为 − f ( p ) -f(p) −f(p) 。

其中， S , T S,T S,T 是另外建立的虚源、虚汇。之后从 S S S 到 T T T 跑最大流，如果从 S S S 出发的所有边都能跑满流量，那么根据流量的平衡性所有到 T T T 的边也一定都能跑满，此时我们可以下结论环流是可行的。

现在来解释一下为什么这么建边：

注意到，原边的下界实际上是 不会 出现在最后的网络流模型中的，最后跑最大流每条边的流量是上下界之差，表示在下界的基础上多流的部分，我们称之为剩余网络。

所以如果 f ( p ) > 0 f(p)>0 f(p)>0 ，说明 p p p 点在流满下界的前提下有流量的堆积，这些流量是需要在剩余网络中流出去的，因此加边 S → p S\rightarrow p S→p 流量为 f ( p ) f(p) f(p) 模拟流量堆积；如果 f ( p ) < 0 f(p)<0 f(p)<0 ，说明 p p p 点在流满下界的前提下流量是亏损的，这些流量是需要在剩余网络中补充进来的，因此加边 p → T p\rightarrow T p→T 流量为 f ( p ) f(p) f(p) 提供 p p p 对流量的吸力。

这么一看，原本觉得反常的加边逻辑，是不是就通顺了。

---

4. 有源汇上下界可行/最大/最小流

下文中 S , T S,T S,T 表示另外建立的虚源、虚汇； s , t s,t s,t 表示原图中的源汇。

1. 可行性：

图中的源 s s s 和汇 t t t 能够凭空产生和处理流量，且 s s s 产生的流量最后将全部流入 t t t ，所以显然可以加边 t → s t\rightarrow s t→s 上下界 ( 0 , ∞ ) (0, \infty) (0,∞) 将有源汇模型转化为无源汇模型。

2. 最大流：

之后如果要求最大流，很显然需要在某一网络上跑最大流算法。

删去判断可行性过程中添加的 虚源和虚汇 及其 附加边 后，在残量网络中尽可能多过一些流量，那么 最大流 + + +原可行流 即为答案。

但考虑到最大流算法的流程， S S S 与 T T T 连接的附加边不需要删，这种只出不进/只进不出、又非源汇点的点是不影响最大流的。

同时，可行流的流量此时就相当于 t → s t\rightarrow s t→s 的 反边 的流量，所以最大流直接以 s s s 和 t t t 为源汇跑即可，其一定会将可行流统计其中。

3. 最小流：

最小流同理，跑 t → s t\rightarrow s t→s 的最大流，但是必须拆掉附加边来跑，最后结果为：原可行流 − - − 最大流。

---

5. 有源汇有负环费用流

普通的费用流可视作所有边自带下界 0 0 0。

参考可行流的处理方法：先把费用为负的边 u → v u\rightarrow v u→v 跑满；同时添加 v → u v\rightarrow u v→u 流量 f f f 费用 ∣ c ∣ |c| ∣c∣，为了跑不满时回退流量。

之后统计每条边的盈亏度，并添加附加边，先从虚源汇跑 maxfow，再以 s s s 和 t t t 跑 maxflow，两次最大流不用累计，但费用是要累计的。

代码如下：模板题 luogu P7173

#include <iostream>
#include <limits>
#include <array>
#include <utility>
#include <queue>using namespace std;
typedef long long LL;
typedef pair <int, int > pii;
const int maxm=1000001;
const int inf=numeric_limits<int>::max();
class netflow{ // 费用流struct edge{int to;int flow;int cost;int nxt;edge(int to=0,int flow=0,int cost=0,int nxt=0):to(to),flow(flow),cost(cost),nxt(nxt){}}e[maxm];
public:int S,T;void addEdge(int x,int y,int f,int c){e[++totEdge]=edge(y,f,c,head[x]);head[x]=totEdge;e[++totEdge]=edge(x,0,-c,head[y]);head[y]=totEdge;return;}pii solve();
private:int totEdge=1;array < int, maxm > head, flow, dist, pre;array < bool ,maxm > inqueue;bool SPFA(int st);
};
bool netflow::SPFA(int st){queue <int> q;flow.fill(inf);dist.fill(inf);q.push(st);dist[st]=0;inqueue[st]=true;pre[T]=0;while(q.empty()==false){int k=q.front();q.pop();inqueue[k]=false;for(int i=head[k];i;i=e[i].nxt){int v=e[i].to;if(e[i].flow && dist[v]>dist[k]+e[i].cost){dist[v]=dist[k]+e[i].cost;flow[v]=min(flow[k],e[i].flow);pre[v]=i;if(!inqueue[v])inqueue[v]=true,q.push(v);}}}return !!pre[T];
}
pii netflow::solve()
{int maxflow=0,mincost=0;while(SPFA(S)){maxflow+=flow[T];mincost+=flow[T]*dist[T];int x=T;while(x!=S){e[pre[x]].flow-=flow[T];e[pre[x]^1].flow+=flow[T];x=e[pre[x]^1].to;}}return make_pair(maxflow,mincost);
}
netflow net;
const int maxn=201;
array <int ,maxn > flow;
int main()
{// freopen("test.in","r",stdin);cin.tie(nullptr)->sync_with_stdio(false);int n,m,s,t;cin>>n>>m>>s>>t;int maxflow=0, mincost=0;net.S=0, net.T=n+1;for(int i=1,x,y,f,c;i<=m;i++){cin>>x>>y>>f>>c;if(c>0)net.addEdge(x, y, f, c);else{mincost+=c*f, flow[x]-=f, flow[y]+=f; // 跑满负权边，统计盈亏度net.addEdge(y, x, f, -c);}}for(int i=1;i<=n;i++){if(flow[i]>0) net.addEdge(net.S, i, flow[i], 0);else if(flow[i]<0) net.addEdge(i, net.T, -flow[i], 0);}pii tmp=net.solve();mincost+=tmp.second;net.S=s, net.T=t;tmp=net.solve();maxflow=tmp.first, mincost+=tmp.second; // 最大流不累计，费用累计cout<<maxflow<<" "<<mincost<<endl;return 0;
}

---

6. 有上下界最小费用可行/最大流

1. 可行流

   和（无/有源汇）有上下界可行流的原理相同，也是拆成两个网络。

   所有附加边的费用设为 0 0 0，最后的费用是下界跑满的费用，加上在剩余网络上从虚源虚汇开始，跑费用流后得到的费用之和。

   注意，这里求出的是满足最小费用的 可行流，而不是 有上下界最小费用最大流。

2. 最大流

   依然类似的处理，在可行流的基础上，再从原图的源汇 s s s 和 t t t 开始跑一次最小费用最大流。

   依然是最大流不累计，费用累计。

   最后得出费用为：下界跑满 + + + 剩余网络 虚源虚汇费用（可行流费用）+ 残量网络 真源汇最小费用最大流 费用；

   流量为：残量网络 真源汇最小费用最大流 流量

---

7. 最小割树

最小割可以用最大流最小割定理，转化为最大流。

简单说来，最小割树解决的问题是，频繁地询问某两点之间的最小割。

首先是一个定理：在一个 n n n 个点的图 G G G 上，本质不同的最小割只有至多 n − 1 n−1 n−1 种，因此一定可以形成一棵树。

其次，对于某个最小割 c u t ( u , v ) cut(u,v) cut(u,v) ，隔开后任意和 u u u 联通的点 x x x 与 任意和 v v v 联通的点 y y y 之间的最小割 c u t ( x , y ) cut(x,y) cut(x,y) 必然满足 c u t ( x , y ) ≤ c u t ( u , v ) cut(x,y)\le cut(u,v) cut(x,y)≤cut(u,v) ，否则直接将 u , v u,v u,v 割开就是更优的情况。

基于此，最小割树的构造方法是：

1. 任意选两个点 u , v u,v u,v 求其最小割，在树上连结 u → v u\rightarrow v u→v 长度为 c u t ( u , v ) cut(u,v) cut(u,v) 的边；
2. 递归割开后和 u , v u,v u,v 联通的点集，重复上过程直至点集大小为 1 1 1 时返回；

查询最小割也很简单，只要查询最小割树上两点间路径上的最小值即可。

求最小割时，切记每次求取之前都要清空最大流。

代码如下：

#include <iostream>
#include <queue>
#include <array>
#include <limits>
using namespace std;
const int inf = numeric_limits<int>::max();
typedef vector <int> vec;class netFlow{ // 最大流static const int maxn = 201, maxm = 6001;struct edge{int nxt, to, flow, cap;edge(int nxt = 0, int to = 0, int flow = 0, int cap = 0):nxt(nxt), to(to), flow(flow), cap(cap){}};
public:int S, T;void adeEdge(int x, int y, int f){e[++totEdge] = edge(head[x], y, f, f);head[x] = totEdge;e[++totEdge] = edge(head[y], x, f, f);head[y] = totEdge;return;}bool bfs(int s, int t){queue <int> q;level.fill(0);q.push(s);level[s] = 1;while(!q.empty()){int k = q.front();q.pop();for(int i = head[k]; i; i = e[i].nxt){int v = e[i].to;if(!level[v] && e[i].flow){level[v] = level[k] + 1;q.push(v);}}}return !!level[t];}int dfs(int u, int flow){if (u == T || !flow) return flow;int ret = 0;for(int i=head[u]; i; i = e[i].nxt){int v = e[i].to;if(level[u] == level[v]-1  && e[i].flow){int now = dfs(v, min(flow, e[i].flow));if(now){ret += now;flow -= now;e[i].flow -= now;e[i^1].flow += now;if(!flow) return ret;}else level[v] = 0;}}return ret;}int solve(int s, int t){int result = 0;S = s, T = t;while(bfs(s, t)){result += dfs(s, inf);}return result;}friend void split(netFlow&, vec&);
private:array <int, maxn > head, level;int totEdge = 1;array <edge, maxm > e;
};
const int maxn = 201;
namespace Tree{ // 最小割树命名空间struct edge{int nxt, to, len;edge(int nxt = 0, int to = 0, int len = 0):nxt(nxt), to(to), len(len){}};array <edge, maxn<<1 > e;array <int, maxn > head;int totEdge = 1;void addEdge(int x, int y, int len){// cout << x << " " << y << " " << len << endl;e[++totEdge] = edge(head[x], y, len);head[x] = totEdge;return;}
};
void split(netFlow& net, vec& v) // 划分点集
{if(v.size() == 1) return;for(int i=2; i<=net.totEdge; i++) // 每次跑最小割之前都要清空net.e[i].flow = net.e[i].cap;int tmp = net.solve(v.cbegin()[0], v.cend()[-1]);Tree::addEdge(v.cend()[-1], v.cbegin()[0], tmp); // 在最大流树上加边Tree::addEdge(v.cbegin()[0], v.cend()[-1], tmp);vec a, b;for(int p: v) // 最大流算法结束前的最后一次一定是 bfs ，此时 level 不是初始值的都是和源点联通的if(!net.level[p]) b.push_back(p);else a.push_back(p);split(net, a), split(net, b);return;
}
netFlow net;
int main()
{int n, m, x, y, f;cin >> n >> m;for(int i=1; i<=m; i++){cin >> x >> y >> f;net.adeEdge(x, y, f);}vec point;for(int i=1; i<=n; i++)point.push_back(i); // 初始化点集split(net, point);return 0;
}

---

小结

以上是作者认为比较常用的 板子 或 模型。

一些模型并没有放代码，是因为我觉得，这些模型中重要的是思想，只要用 最大流/费用流 稍加修改就可以完成。

网络流题目中最重要的还是建模；但是也需要了解我们的板子能解决哪些问题，才能知道我们建模需要建到什么形式。

很多地方并没有严格证明，也没有使用最快的算法，感兴趣的读者可自行查阅了解。

博主日后也许会更新关于网络流算法遭遇卡常时的优化办法，，，也有可能不会（doge）

代码、论述如有错误，欢迎各位读者指出。