网络流
一、网络最大流
（从学委那里拿的动图。）
\text{Dinic}
/*
Dinic
在残留网络和 EK 的基础上，按照源点到该点的距离进行分层，每次寻找增广路径时，
保证每次都是从一层走到下一层。每次可寻找到多条增广路径
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define maxn 205
#define maxm 10005
#define rep(i, a, b) for(int i = a; i <= b; ++i)
int n, m, s, t;
int cnt = 1, hd[maxn];
struct node{
int to, nxt, val;
}e[maxm];
int dep[maxn], ans;
int u, v, w;
inline void add(int u, int v, int w)
{
e[++cnt].to = v;
e[cnt].nxt = hd[u], e[cnt].val = w;
hd[u] = cnt;
}
inline bool bfs()
{
queue <int> q;
memset(dep, 0, sizeof dep);
dep[s] = 1, q.push(s);//注意初始源点为第一层
while(!q.empty())
{
int u = q.front();
q.pop();
for(int v, i = hd[u]; i; i = e[i].nxt)
{
if(e[i].val/*该边能走*/ and !dep[v = e[i].to]/*没有访问过*/)
{
dep[v] = dep[u] + 1;
q.push(v);
}
}
}
if(dep[t]/*汇点可以到达，说明此时网络中有增广路径*/) return 1;
return 0;
}
inline int dinic(int u, int in/*从源点到达 u 点的流量*/)
{
if(u == t/*到达汇点*/) return in;
int out = 0;//记录能从 u 点流出的流量
for(int i = hd[u]; i and in/*当前还有流量可以流走*/; i = e[i].nxt)
{
int v = e[i].to;
if(dep[v] == dep[u] + 1/*只能往下一层走*/ and e[i].val/*当前边可以走*/)
{
int res = dinic(v, min(e[i].val, in)/*更新流入量*/);
e[i].val -= res, e[i ^ 1].val += res/*更新当前边流量*/;
in -= res, out += res;
}
}
if(!out/*没有流可以从 u 点流出去*/) dep[u] = 0/*优化，下一次不会再经过此点*/;
return out;
}
signed main()
{
scanf("%lld %lld %lld %lld", &n, &m, &s, &t);
rep(i, 1, m)
{
scanf("%lld %lld %lld", &u, &v, &w);
add(u, v, w), add(v, u, 0);
//残留网络，同时建反边，边权为 0，并以此判断该边能否通过
}
while(bfs()) ans += dinic(s, 1e16);//每次找完当前情况下的增广路径之后，重新分层
printf("%lld\n", ans);
return 0;
}1、当前弧优化
“
注意在 DFS 中用
从某种意义上来说，它和求最短路相似。所以直接用
代码 + 注释
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
#define int long long
#define rep(i, a, b) for(int i = a; i <= b; ++i)
const int maxn = 5e3 + 5;
const int maxm = 1e5 + 5;
int n, m, s, t;
bool vis[maxn];
int incf[maxn], dis[maxn], pre[maxn], mxfl, mxcs;
int cnt = 1, hd[maxn];
struct node{
int to, nxt, flw, cst;
}e[maxm];
inline void add(int u, int v, int w, int c)
{
e[++cnt].to = v;
e[cnt].nxt = hd[u], e[cnt].flw = w, e[cnt].cst = c;
hd[u] = cnt;
}
inline bool spfa()
{
queue <int> q;
memset(dis, 0x3f, sizeof dis);
memset(vis, 0, sizeof vis);
q.push(s), vis[s] = 1, dis[s] = 0, incf[s] = 2147483647;
while(!q.empty())
{
int u = q.front();
q.pop(), vis[u] = 0;
for(int i = hd[u], v; i; i = e[i].nxt)
{
if(!e[i].flw) continue;//注意不要漏掉
if(dis[v = e[i].to] > dis[u] + e[i].cst)
{
dis[v] = dis[u] + e[i].cst;//记录一路上的费用
incf[v] = min(incf[u], e[i].flw);//最终能流到 v点的流量
pre[v] = i;//记录路径
if(!vis[v]) vis[v] = 1, q.push(v);
}
}
}
if(dis[t] != dis[n + 2]) return true;
return false;
}
inline void mcmf()
{
while(spfa())//多次增广
{
mxfl += incf[t];
mxcs += incf[t] * dis[t];
int x = t, i;
while(x != s)
{
i = pre[x];
e[i].flw -= incf[t], e[i ^ 1].flw += incf[t];
x = e[i ^ 1].to;
}
}
}
signed main()
{
scanf("%lld %lld %lld %lld", &n, &m, &s, &t);
rep(i, 1, m)
{
int u, v, w, c;
scanf("%lld %lld %lld %lld", &u, &v, &w, &c);
add(u, v, w, c), add(v, u, 0, -c);
}
mcmf();
printf("%lld %lld\n", mxfl, mxcs);
return 0;
}例：【LG-P1251】餐巾计划问题（题解）
预流推进
这是一个解决最大流、时间最快、代码较长的算法。
算法详情及解法见：P4722 【模板】最大流 加强版 / 预流推进 题解—— by 531
\text{HLPP} 思路
按照众多大佬所说的那样，
注意，在此算法中，我们的目标是图中所有中转点最后存储的流量为 0。
在此过程中，为了防止
那为什么它会比其他解决最大流问题的算法快呢？
首先，在这里我们只用运行一次
其次，因为它是一步一步将流向下推，所以不用多次
整体代码：
#include<bits/stdc++.h>
using std::min;
using std::vector;
using std::queue;
using std::priority_queue;
#define maxn 2005
#define maxm 200005
#define inf 2147483647
#define rep(i, a, b) for(register int i = a; i <= b; ++i)
int n, m, s, t;
int cnt = 1, hd[maxn];
struct node{
int to, nxt, f;
}e[maxm << 1];
int p[maxn], h[maxn], gap[maxm];
bool inq[maxn];
queue <int> q;
struct cmp{
inline bool operator () (int a, int b) const//重写仿函数
{
return h[a] < h[b];
}
};
priority_queue <int, vector<int>, cmp> pq;
int u, v, w;
inline int read()
{
int x = 1, s = 0;
char ch = getchar();
while(ch < '0' or ch > '9') {if(ch == '-') x = -1; ch = getchar();}
while(ch >= '0' and ch <= '9') s = s * 10 + ch - '0', ch = getchar();
return x * s;
}
inline void add(int u, int v, int w)
{
e[++cnt] = (node){v, hd[u], w};
hd[u] = cnt;
e[++cnt] = (node){u, hd[v], 0};
hd[v] = cnt;
}
inline bool bfs()
{
rep(i, 1, n) h[i] = inf;
h[t] = 0, q.push(t);
while(!q.empty())
{
int u = q.front();
q.pop();
for(int i = hd[u], v; i; i = e[i].nxt)
if(e[i ^ 1].f and h[v = e[i].to] > h[u] + 1)
h[v] = h[u] + 1, q.push(v);
}
return h[s] == inf ? 0 : 1;
}
inline void push(int nw)
{
for(int i = hd[nw], v; i; i = e[i].nxt)
{
if(!p[nw]) return;
if(h[v = e[i].to] + 1 != h[nw] or !e[i].f) continue;
int d = min(p[nw], e[i].f);
p[nw] -= d, p[v] += d, e[i].f -= d, e[i ^ 1].f += d;
if(v != s and v != t and !inq[v])
pq.push(v), inq[v] = 1;
}
}
inline void updt(int u)
{
h[u] = inf;
for(int i = hd[u], v; i; i = e[i].nxt)
{
if(e[i].f and h[v = e[i].to] + 1 < h[u])
h[u] = h[v] + 1;
}
}
inline int hlpp()
{
if(!bfs()) return 0;
h[s] = n;
for(int i = hd[s], v, d; i; i = e[i].nxt)
{
if(d = e[i].f)
{
p[v = e[i].to] += d, p[s] -= d;
e[i].f -= d, e[i ^ 1].f += d;
if(v != s and v != t and !inq[v]) pq.push(v), inq[v] = 1;
}
}
rep(i, 1, n) if(h[i] != inf) gap[h[i]] += 1;
while(!pq.empty())
{
int u = pq.top();
pq.pop(), inq[u] = 0, push(u);
if(!p[u]) continue;
if(!--gap[h[u]])
{
rep(i, 1, n)
if(i != s and i != t and h[i] > h[u] and h[i] < n + 1)
h[i] = n + 1;
}
updt(u), gap[h[u]] += 1, pq.push(u), inq[u] = 1;
}
return p[t];
}
int main()
{
n = read(), m = read(), s = read(), t = read();
rep(i, 1, m)
u = read(), v = read(), w = read(), add(u, v, w);
printf("%d\n", hlpp());
return 0;
}1、分层图
一些题目中，在原来单纯网络流的基础上又加了一个状态，这时就得再用分层图了。
例：P4009 汽车加油行驶问题
一道分层图类型很好的例题。分层后可以使用最短路
回到题目。如果没有油量的限制，很明显就是一道费用流。但是在有了油量的限制之后，车到达每一个节点时的状态（即当时剩余的油量）就不同，就不能将它们归为一个点处理。
所以，在油量上限为
有了这个基础理解之后，剩下的建边根据题意即可。
此题
注意数组边界大小；此处没有放最小费用流板子，只放了建边过程。
#include<bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i <= b; ++i)
#define maxn 110005
#define maxm 1100100
#define inf 2147483647
const int c = 10000;
int n, K, A, B, C;
int cnt = 1, hd[maxn];
struct node{
int to, nxt, flw, cst;
}e[maxm];
int s, t = maxn - 1;
int dis[maxn];
bool vis[maxn];
int incf[maxn];
int pre[maxn];
inline void add(int u, int v, int f, int c)
{
e[++cnt] = (node){v, hd[u], f, c};
hd[u] = cnt;
e[++cnt] = (node){u, hd[v], 0, -c};
hd[v] = cnt;
}
inline int id(int i, int j)
{
return (i - 1) * n + j;
}
int main()
{
scanf("%d %d %d %d %d", &n, &K, &A, &B, &C);
add(s, id(1, 1)/*起始点，此时汽车为满油，所以在第 0 层*/, 1, 0);
rep(i, 0, K) add(id(n, n) + c * i/*每一层的终点。只要到了终点不论在哪一层都可以结束*/, t, 1, 0);
rep(i, 1, n) rep(j, 1, n)
{
int tmp;
scanf("%d", &tmp);
if(tmp)//如果有油箱
rep(k, 1, K) add(id(i, j) + c * k/*每碰到油箱都要强制加油，回到第 0 层*/, id(i, j), 1, A);
rep(k, 0, K - 1)
{
if(tmp/*油箱*/ and k/*因为强制性加油，所以最后都会回到第 0 层，上面都不考虑*/) break;
if(i + 1 <= n) add(id(i, j) + c * k, id(i + 1, j) + (k + 1) * c/*因为每走一步都在减少油量，所以要向上层连边*/, 1, 0);
if(j + 1 <= n) add(id(i, j) + c * k, id(i, j + 1) + (k + 1) * c, 1, 0);
if(i - 1 >= 1) add(id(i, j) + c * k, id(i - 1, j) + (k + 1) * c, 1, B);
if(j - 1 >= 1) add(id(i, j) + c * k, id(i, j - 1) + (k + 1) * c, 1, B);
}
add(id(i, j) + K * c, id(i, j), 1, A + C);//新建一个油箱并加满油回到第 0 层
}
printf("%d\n", mcmf());
return 0;
}四、最大权闭合子图
1. 概念
-
闭合子图：在原图
G 的闭合子图中，每一个节点，它在G 中所能到达的所有节点都包含在这个子图中。 -
最大权闭合子图：即原图
G 中点权之和最大的闭合子图。
2. 运用
目标：求一图的最大权闭合子图。
<1>
先建立一超级源点和超级汇点。
对于每个带权值的节点：
- 若节点为正，则与超级源点相连，流量为该点权值；
- 反之，则与超级汇点相连，流量为该点权值相反数。
很明显，在不考虑“每个点在
此时，上述的建边方式的原因就清楚明了了：区分开来正负权值的点。
<2>
然后再加上限制，在点和点之间建边。
此时可以隐约发现：我们会使用最小割去求出最大权子图。
割去一些边，使源点与汇点不相连，最后源点所在的那个子图即为原图的最大权闭合子图。
回过头来：这些边的流量是什么？
这些边的流量为
<3>
此时可以发现，被割去的边都是与源点或者汇点相连的边。
-
若一负权值节点与汇点相连的边被割去：
说明此时它放在最大权闭合子图中是最优的状态，但最大权闭合子图的权值和要减去该点权值的绝对值。
-
若一正权值节点与汇点相连的边被割去：
说明此时它不放在最大权闭合子图中是最优的状态，但最大权闭合子图的权值和要减去该点权值。
这样一来，最大权闭合子图的权值和就是：正权值之和 - 最小割。
然后最小割转化为最大流去求解即可。
例题：P2805 [NOI2009] 植物大战僵尸 | P3872 [TJOI2010]电影迷（题解）
五、经典例题
【Luogu-P3324 [SDOI2015] / DSY-1993】星际战争（题解）
——