(G=(V,E))：有向图，s:源点，t:汇点，边权：流量。不存在反向边（存在可以加点）。
可行流 (f)：容量限制，流量守恒对于每个点流入流出相同（不考虑反向边）。
最大流：最大可行流。
残留网络：与可行流一一对应，由原图边和反向边组成，原图边，容量减流量，原图反向边，退流。
原网络的可行流加残留网络的可行流也是原网络的可行流。流量值相加。
增广路径：在残留网络里，沿着边权大于零的边走，如果能到达重点则称为增广路径。
若可行流没有增广路径，则该可行流为最大流。
割：把点集分成两个子集：(S)，(T)，(s∈S)，(t∈T)。
割的容量：由 (S) 指向 (T) 的边权之和。（不考虑反向边）
割的流量：由 (S) 指向 (T) 的流量之和减去由 (T) 指向 (S) 的流量之和。
割的流量一定小于等于割的容量。
最大流小于等于最小割
最大流 (f) 的残留网络中不存在增广路。存在割的流量等于最大流的流量。
(EK) 算法：复杂度 (O(nm^2))。迭代，每次先找一条增广路，更新残留网络，求增广路径上容量的最小值，更新所有正向边减去 (k)，所有反向边增加 (k)，利用一个 (pre) 数组记录一下路径。
const int N = 1e3 + 10;
const int M = 2e4 + 10; //残留网络
const int inf = 1e8;
int n, m, S, T;
int h[N], e[M], f[M], ne[M], idx; //f容量
int q[N], d[N], pre[N];//宽搜队列，记录从起点到当前点的容量最小值
bool st[N];
inline void add(int a, int b, int c){//维护残留网络
e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx ++;//容量
e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++;//反向边容量为0
}
inline bool bfs(){//bfs找增广路
int hh = 0, tt = 0;
memset(st, false, sizeof st);
q[0] = S, st[S] = true, d[S] = inf;
while(hh
(Dinic) 算法：复杂度 (O(n^2m))。
const int N = 1e4 + 10;
const int M = 2e5 + 10;
const int inf = 1e8;
int n, m, S, T;
int h[N], e[M], f[M], ne[M], idx; //f容量
int q[N], d[N], cur[N];//优化
inline void add(int a, int b, int c){//维护残留网络
e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx ++;//容量
e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++;//反向边容量为0
}
//当前弧优化
//记录流满的边数，从下一条边开始枚举
inline bool bfs(){ //判断有无增广路，并建立分层图
int hh = 0, tt = 0;
memset(d, -1, sizeof d);
q[0] = S, d[S] = 0, cur[S] = h[S];
while (hh
用网络流解题，需要可行流与可行解一一对应。
在一个流网络里，所有最大可行流中费用的最小、最大值。
最小费用最大流：退费用，(SPFA)求一条源点到汇点的最短路，更新残留网络，((EK))。
const int N = 5e3 + 10;
const int M = 2e5 + 10;
const int inf = 1e8;
int n, m, S, T;
int h[N], e[M], f[M], w[M], ne[M], idx;
int q[N], d[N], pre[N], incf[N];
//记录推最短路，走到每个点的最大流量
bool st[N];
inline void add(int a, int b, int c, int d){
e[idx] = b, f[idx] = c, w[idx] = d, ne[idx] = h[a], h[a] = idx ++;
e[idx] = a, f[idx] = 0, w[idx] = -d, ne[idx] = h[b], h[b] = idx ++;
}
inline bool spfa(){
int hh = 0, tt = 1;
memset(d, 0x3f, sizeof d);
memset(incf, 0, sizeof incf);
q[0] = S, d[S] = 0, incf[S] = inf;
while(hh != tt){
int t = q[hh ++];
if(hh == N) hh = 0;
st[t] = false;
for(int i = h[t]; ~ i; i = ne[i]){
int ver = e[i];
if(f[i] && d[ver] > d[t] + w[i]){
d[ver] = d[t] + w[i];
pre[ver] = i;
incf[ver] = min(f[i], incf[t]);
if(!st[ver]){
q[tt ++] = ver;
if(tt == N) tt = 0;
st[ver] = true;
}
}
}
}
return incf[T] > 0;
}
inline void EK(int &flow, int &cost){
flow = cost = 0;
while(spfa()){
int t = incf[T];
flow += t, cost += t * d[T];
for(int i = T; i != S; i = e[pre[i] ^ 1]){
f[pre[i]] -= t, f[pre[i] ^ 1] += t;
}
}
}
signed main(){
read(n), read(m), read(S), read(T);
memset(h, -1, sizeof h);
while(m --){
int a, b, c, d;
read(a), read(b), read(c), read(d);
add(a, b, c, d);
}
int flow, cost;
EK(flow, cost);
print(flow), cout << " ", print(cost);
return 0;
}
Original: https://www.cnblogs.com/William-Sg/p/16406987.html
Author: Altwilio
Title: 网络流
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/605269/
转载文章受原作者版权保护。转载请注明原作者出处！