网络流
基础知识
流网络
流网络是一个有向图$G=(V,E)$ 每条边$(u,v)$都具有一个权值$c(u,v)$,称为容量，同时规定若$(u,v) \notin E$,则有$c(u,v)=0$,网络中有两个特殊的点，源点$s$和汇点$t$。可以证明任意一个多源汇流网络得最大流问题都可以转换成单源汇流网络的最大流问题，所以一般只考虑单源汇问题，同时对于重边我们对可以通过加点的方式转换成非重边，综上一般我们的对象都可以处理成单源汇无反向边的网络。
可行流
网络的流(flow)是一个实值函数 $f: V\times V\rightarrow R $,同时满足
- 容量限制：对于每一条边，经过改边的流量不得超过该边的容量 e.g $f(u,v)<c(u,v)$
- 斜对称性：$f(u,v)=-f(v,u)$
- 流守恒性：$\forall v\in V-\{s,t\},\ \sum_{e\in N^+(v)}f(e)-\sum_{e\in N^-(v)}f(e)=0$ 也就是其他点的净流量等于0
同时我们规定可行流得值等于 $|f|=\sum_{v\in V}f(s,v)$ 也就是流值等于源点的流入值同时也等于汇点得流出值。
最大流
最大流指的是流值最大的可行流
流网络的其他概念
净流量： $f(X,Y)=\sum_{u\in X,v\in Y}f(u,v)-\sum_{v\in X,u\in Y}f(u,v)$
性质 ：
- $\forall X \subseteq V$ 有 $f(X,X)=0$ ，根据流守恒可知此定理一定成立
- $\forall X,Y\subseteq V,$有$f(X,Y)=-f(Y,X)$
- $\forall X,Y,Z \subseteq V$,其中$X\cap Y=\emptyset$,$f(X\cap Y,Z)=f(X,Z)+f(Y,Z)$
这些性质在后面求证最小割的一些性质会很有用
残留网络
残留网络是对于一个流函数而言的， $c_f(u,v)=c(u,v)-f(u,v)$
下面证明 $f+f^{‘}$依然是可行流
- 容量限制
$f{‘’}(u,v)=f(u,v)+f^{‘}(u,v)<=f(u,v)+c(u,v)-f(u,v)=c(u,v)$
- 流守恒性
$\forall x\in V, f^{‘’}_净(x)=f_{净}^{‘}(x)+f_{净}(x)=0$
综上残留网络的可行流加上原网络的可行流依然是可行流
增广路径
增广路对应于残留网络中$G_f$上源点$s$到汇点$t$的一天简单路
显然我们可以利用增广路构造如下的一个可行流来使得其和原网络的可行流组成的新的可行流拥有更大的流量,假设$p$是一条增广路
$$
f_p(u,v)=
\begin{cases}
c_f(p) &(u,v)\in p\\\\
-c_f(p) &(v,u)\in p\\\\
0 &else
\end{cases}
$$
根据前面的性质可行流$f^{‘}=f_p+f$依然是原网络的一个可行流同时有$|f^{‘}|=|f|+|f_p|$
割
割的定义
网络流$G=(V,E)$的割$[S,T]$是点集$V$的一个划分，使得$s\in S,t\in T$,割是满足条件 $(u,v)\in E,u\in S,v\in T$的有向边的一个集合，同时称 $c(S,T)=\sum_{u\in S,v\in T}c(u,v)$为割的容量，$f(S,T)=\sum_{u\in S,v\in T}f(u,v)-\sum_{u\in T,v\in S}f(u,v)$为割的干净流量。最小割指的是容量最小的割
其实一般向引入这种情况都是有对偶问题(不然引入干嘛)，因此我们可以思考割与流的关系。
性质：
- 网络流$G=(V,E)$中，$\forall\ [S,T]\ \forall f, f(S,T)=|f|$。
- $\forall [S,T ]\ \forall f,f(S,T)<=c[S,T]$
性质一证明：
$$
\begin{aligned}
f(S,V)&=f(S,S\cup T)\\\\
&=f(S,S)+f(S,T)\\\\
&=f(S,T) \\\\
f(S,T)&=f(S,V)\\\\
&=f(s,V)+f(S-\{s\},V)\\\\
&=f(s,V)+\sum_{x\in S-\{s\}}(\sum_{v\in V,(x,v)\in E}f(x,v)-\sum_{v\in V,(v,x)\in E}f(v,x))\\\\
&=f(s,V)\\\\
&=|f|
\end{aligned}
$$
性质二证明：
$$
\begin{aligned}
|f|=f(S,T)=\sum_{v\in S,u\in T}f(u,v)<=\sum_{u\in S,v\in T}c(u,v)=c[S,T]
\end{aligned}
$$
最大流最小割定理
命题（1）可行流$f$是最大流
（2）可行流的残留网络中不存在增广路
（3）存在某个割$[S,T],|f|=c(S,T)$ 等价
证明：
$(1)\Rightarrow(2)$
反证法：假设残留网络中存在增广路 $p$则有$|f^{‘}|=|f|+|f_p|>|f|$显然矛盾
$(3)\Rightarrow(1)$
$\forall f,c[S,T]>=|f|$，又若有$|f|=c[S,T]$这$|f|=max(|f|)$ 所以$f$就是最大流
$(2)\Rightarrow(3)$
构造$S=\{v\in V|\exists p_{s,v}\in G_f\},T=V-S$
首先由于残流网络中不存在从$s到t$的增广路,所以$t\in T$,同时$S\cap T=\emptyset,S\cup T=V$,所以$[S,T]$是一个割
$\forall u\in S,v\in T$，显然有$f^{‘}(u,v)=0,$t果$同时如果f(u,v)\neq c(u,v)$则在残留网络中有$u\in S,f^{‘}(u,v)>0$则有$v\in S$,与条件矛盾所以$\forall v\in S,u\in T,f(u,v)=c(u,v)$,所以有$f(S,T)=|f|=c[S,T]$
综上得证
EK算法
// CREATED BY MASHIROYUKI
#include <bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#pragma GCC optimize("O3")
#define rep(i, x, n) for(int i = x; i <= n; i ++ )
#define downrep(i, x, n) for(int i = n; i >= x; i -- )
template<typename T> void debug(T x) {cout << "#debug: " << x << endl;}
template<typename T> void debug(T x, T y) {cout << "#debug: " << x << " " << y << endl;}
template<typename T>
void read(T &x){
x = 0;
char ch = getchar();
while(!isdigit(ch)) ch = getchar();
while(isdigit(ch)){
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
}
typedef long long ll;
typedef double db;
const int mod = 1e9 + 7;
const int N = 1e6 + 10,inf=2e9;
int e[N],ne[N],vol[N],h[N],idx=2;
int flow[N],pre[N];
int n,m,st,ed;
queue<int> q;
inline void add(int a,int b,int c) {
e[idx]=b,ne[idx]=h[a],vol[idx]=c,h[a]=idx++;
}
bool bfs() {
memset(pre,0,sizeof pre);
while(q.size()) q.pop();
q.push(st);
flow[st]=inf;
while(q.size()) {
int u=q.front();q.pop();
for(int i=h[u];~i;i=ne[i]) {
int j=e[i];
if(!pre[j]&&vol[i]) {
pre[j]=i;
flow[j]=min(flow[u],vol[i]);
if(j==ed)return true;
q.push(j);
}
}
}
return false;
}
ll EK() {
ll res=0;
while(bfs()) {
res+=flow[ed];
for(int i=ed;i!=st;i=e[pre[i]^1]) {
vol[pre[i]]-=flow[ed],vol[pre[i]^1]+=flow[ed];
}
}
return res;
}
void solve()
{
read(n),read(m),read(st),read(ed);
memset(h,-1,sizeof h);
rep(i,1,m) {
int u,v,w;
read(u),read(v),read(w);
add(u,v,w);add(v,u,0);
}
printf("%lld\n",EK());
}
signed main()
{
//IO
solve();
return 0;
}
参考y总的讲解和《最大流最小割在信息学中的应用》，蒟蒻的写的比较差还请各位指正
DINIC算法
// CREATED BY MASHIROYUKI
#include <bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#pragma GCC optimize("O3")
#define rep(i, x, n) for(int i = x; i <= n; i ++ )
#define downrep(i, x, n) for(int i = n; i >= x; i -- )
template<typename T> void debug(T x) {cout << "#debug: " << x << endl;}
template<typename T> void debug(T x, T y) {cout << "#debug: " << x << " " << y << endl;}
template<typename T>
void read(T &x){
x = 0;
char ch = getchar();
while(!isdigit(ch)) ch = getchar();
while(isdigit(ch)){
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
}
typedef long long ll;
typedef double db;
const int mod = 1e9 + 7;
const int N = 2e5 + 10,INF=1e9;
int e[N],ne[N],h[N],idx;
int vol[N],cur[N],d[N];//当前弧优化以及深度数组
int n,m,S,T;
queue<int> q;
void add(int a,int b,int w) {
e[idx]=b,ne[idx]=h[a],vol[idx]=w,h[a]=idx++;
}
int dfs(int u,int up) {
if(u==T) return up;
int flow=0; //表示通过当前点的最大流量
for(int i=cur[u];~i&&flow<up;i=ne[i]) {
cur[u]=i;
int j=e[i];
if(d[j]==d[u]+1&&vol[i]) {
int t=dfs(j,min(vol[i],up-flow));
if(!t) d[j]=-1;
vol[i]-=t,vol[i^1]+=t,flow+=t;
}
}
return flow;
}
bool bfs() {
memset(d,-1,sizeof d);
while(q.size())q.pop();
q.push(S),cur[S]=h[S],d[S]=0;
while(q.size()) {
int u=q.front();
q.pop();
for(int i=h[u];~i;i=ne[i]) {
int j=e[i];
if(d[j]==-1&&vol[i]) {
d[j]=d[u]+1;
cur[j]=h[j];
if(j==T) return true;
q.push(j);
}
}
}
return false;
}
int dinic() {
ll res=0,flow;
bfs();
while(bfs()) while((flow=dfs(S,INF))) res+=flow; //分层的同时判断是否有增广路
return res;
}
void solve()
{
read(n),read(m),read(S),read(T);
memset(h,-1,sizeof h);
rep(i,1,m) {
int u,v,w;
read(u),read(v),read(w);
add(u,v,w);add(v,u,0);
}
for(int i=h[S];~i;i=ne[i]);
printf("%d\n",dinic());
}
signed main()
{
//IO
solve();
return 0;
}
有源汇上下界最大流
// CREATED BY MASHIROYUKI
#include <bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#pragma GCC optimize("O3")
#define rep(i, x, n) for(int i = x; i <= n; i ++ )
#define downrep(i, x, n) for(int i = n; i >= x; i -- )
template<typename T> void debug(T x) {cout << "#debug: " << x << endl;}
template<typename T> void debug(T x, T y) {cout << "#debug: " << x << " " << y << endl;}
template<typename T>
void read(T &x){
x = 0;
char ch = getchar();
while(!isdigit(ch)) ch = getchar();
while(isdigit(ch)){
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
}
typedef long long ll;
typedef double db;
const int mod = 1e9 + 7;
const int N = 1e5 + 10,INF=1e9+10;
int e[N],ne[N],h[N],vol[N],l[N],idx;
int cur[N],d[N],dif[N];
int n,m,ss,tt,S,T;
queue<int>q;
inline void add(int a,int b,int c,int d) {
e[idx]=b,ne[idx]=h[a],l[idx]=c,vol[idx]=d-c,h[a]=idx++;
e[idx]=a,ne[idx]=h[b],l[idx]=0,vol[idx]=0,h[b]=idx++;
}
int dfs(int u,int up) {
if(u==T) return up;
int flow=0;
for(int i=cur[u];~i&&flow<up;i=ne[i]) {
cur[u]=i;
int j=e[i];
if(d[j]==d[u]+1&&vol[i]) {
int t=dfs(j,min(vol[i],up-flow));
if(!t)d[j]=-1;
vol[i]-=t,vol[i^1]+=t,flow+=t;
}
}
return flow;
}
bool bfs() {
memset(d,-1,sizeof d);
while(q.size())q.pop();
q.push(S),d[S]=0,cur[S]=h[S];
while(q.size()) {
int u=q.front();q.pop();
for(int i=h[u];~i;i=ne[i]) {
int j=e[i];
if(d[j]==-1&&vol[i]) {
d[j]=d[u]+1;
cur[j]=h[j];
if(j==T) return true;
q.push(j);
}
}
}
return false;
}
ll dinic() {
ll res=0;
while(bfs())res+=dfs(S,INF);
return res;
}
void solve()
{
memset(h,-1,sizeof h);
read(n),read(m),read(ss),read(tt);
S=0,T=n+1;
rep(i,1,m) {
int a,b,c,d;
read(a),read(b),read(c),read(d);
add(a,b,c,d);
dif[a]-=c,dif[b]+=c;
}
int tot=0;
rep(i,1,n)
if(dif[i]>0)add(S,i,0,dif[i]),tot+=dif[i];
else if(dif[i]<0)add(i,T,0,-dif[i]);
add(tt,ss,0,INF);
if(dinic()!=tot) {
puts("No Solution");
return;
}
ll res=vol[idx-1];
vol[idx-1]=vol[idx-2]=0;
S=ss,T=tt;
res+=dinic();
printf("%lld\n",res);
}
signed main()
{
//IO
solve();
return 0;
}
后续在更新一下预流推进吧
%%%tql