网络流
标签（空格分隔）： 图论
网络流
实则为一种建模思想，可以将一些问题转换为图来解答
图的定义
一个图 (G) 是一个二元组，记为 ((V,E)),或者记作 (G(V,E)),其中 (V) 为有限非空集合，成为 (G) 的顶点集，(V) 中的元素成为节点或者顶点，(E) 称为 (G) 的边的集合，(forall e_i in E),都有 (V) 中的结点与之对应，称 (e_i) 为 (G) 的边。
(E) 是边集合，(V) 是点集合
网络流的基本概念
-
容量：网络中的每条有向边 (f(x,y)) 都有一个给定的权值，称为边的容量，记为(c(x,y)) 。也可以(ein E) , (c(e)) 容量，(f(e)) 流量
-
源点、汇点：网络中的两个特殊节点。流量从源点产生，最后全部归于汇点。源点用 (S) 表示，汇点用 (T) 表示。
-
流量：对于网络中的每条边 ((x,y))， (f(x,y))被称为该边的流量。流量需要满足以下三条性质：
-
容量限制：对于每条边，流经该边的流量不得超过该边的容量，即(f(x,y)leq c(x,y)) 。
-
斜对称性：每条边的流量与其相反边的流量之和为 0，即 (f(x,y)=-f(x,y))。
-
流量守恒：从源点流出的流量等于汇点流入的流量。
-
-
满足这个规则的网络叫做流网络 (G)
- (V_xin V-(s,t),sum_{(v,x)in E}^{}f(v,x)=sum_{(x,v)in E}^{}f(x,v))
-
所有可能出现的流量的情况，称为可行流 (f) ,其中(0) 流也是可行流
-
最大可行流为(|f|_{max})
形象的图
抽象的图
最大流为 (10)
-
两个可行流方案相加，是一个新的可行流方案
(|f_1+f_2|=|f_1|+|f_2|) -
在原图 (G) 上增添反向边，根据原图的可行流 (f) ，对应一个新图：残余网络 (G_f)。记录每条边的剩余容量
-
反向边只存在于参与网络，在原图上并不存在
-
可行流各不相同，参与网络也各不相同
-
-
在参与网络上寻找 (s o t) 的路径为增广路
- 残余网络中不存在增广路的充要条件是当前流已是最大流
常见问题
最大流，最小割，费用流
最大流算法
贪心算法：
1、从 (s o t)寻找一条路径，路径上所有的边满
足容量限制 (f(e)leq c(e))
2、如果不存在满足条件的路径，则结束算法。否
则沿着这条路径尽可能的增加流量，返回第 (1) 步。
Ford-Fulkerson(FF)算法
基于增广路的最大流方法
时间复杂度:每次 (DFS) 为 (O(m)),设最大流的流量为 (f) ,由于每次流量至少增加 (1) ,总时间复杂度为(O(fm))
显然慢成狗/ww
Edmond-Karp(EK)算法
最短路增广算法（(BFS)算法）
#include<iostream>
#include<cstring>
#include<queue>
#define int long long
using namespace std;
const int N=1e2+9;
const int M=5e3+9;
struct node{
int c;
int last;
int to;
}e[N];
int n,m,s,t,cnt;
int maxflow;
int head[N];
int c[M];
void add(int from,int to,int dis)
{
e[++cnt].last=head[from];
e[cnt].to=to;
e[cnt].c=dis;
head[from]=cnt;
e[++cnt].last=head[to];
e[cnt].to=from;
e[cnt].c=0;
head[to]=cnt;
}
int vis[N],pre[N];//访问，前驱
int incf[N];//可增加流量数组
const int inf=1<<29;
bool bfs()
{
memset(vis,0,sizeof(vis));
queue<int> q;
q.push(s);
vis[s]=1;incf[s]=inf;//发出的从无限大凯始
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head[u];i;i=e[i].last)
{
if(e[i].c)//有容量
{
int v=e[i].to;
if(vis[v]) continue;
incf[v]=min(incf[u],e[i].c);
pre[v]=i;//记录到达点的边的编号
q.push(v);
vis[v]=1;
if(v==t) return 1;//如果到了终点
}
}
}
return 0;
}
void update()
{
int u=t;//从后往前找
while(u!=s)
{
int i=pre[u];
e[i].c-=incf[t];//反方向边编号为奇数，正方向为偶数
e[i^1].c+=incf[t];
u=e[i^1].to;
}
maxflow+=incf[t];
}
signed main()
{
cin>>n>>m>>s>>t;
cnt=1;
maxflow=0;
while(m--)
{
int u,v,c;
cin>>u>>v>>c;
add(u,v,c);
}
while(bfs()) update();
cout<<maxflow<<endl;
}
Dinic算法
基于分层图的多路增广算法
算法思想：
- 在残余网络上，用BFS从源点 (s) 到汇点 (t) 构造
分层图； - 在当前分层图上，使用DFS进行多路增广，
在回溯时实时更新剩余容量。
直至在残余网络中，无法从源点 (s) 到达汇点 (t)。
当前弧优化：记录一下当前没有满流的边
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#define int long long
using namespace std;
const int N=1e4+9;
const int M=1e5+9;
const int inf=2e9+9;
struct node{
int last;
int to;
int c;
}e[M];
int cur[N],head[N],d[N];
int n,m,s,t,cnt;
void add(int from,int to,int dis)
{
e[++cnt].last=head[from];
e[cnt].to=to;
e[cnt].c=dis;
head[from]=cnt;
}
bool bfs()
{
memset(d,-1,sizeof(d));
queue<int> q;
q.push(s);
d[s]=0;
cur[s]=head[s];
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head[u];i;i=e[i].last)
{
int v=e[i].to;
int w=e[i].c;
if(d[v]==-1&&w)
{
d[v]=d[u]+1;
cur[v]=head[v];
q.push(v);
if(v==t) return true;
}
}
}
return false;
}
int dfs(int u,int lim)
{
int flow=0;
if(u==t) return lim;
for(int i=cur[u];i&&flow<lim;i=e[i].last)
{
cur[u]=i;//当前弧优化
int v=e[i].to;
int w=e[i].c;
if(w&&d[v]==d[u]+1)
{
int f=dfs(v,min(w,lim-flow));
if(!f) d[v]=-1;
e[i].c-=f;
e[i^1].c+=f;
flow+=f;
}
}
return flow;
}
int dinic()
{
int maxflow=0;
int flow=0;
while(bfs())
while(flow=dfs(s,inf))
maxflow+=flow;
return maxflow;
}
signed main()
{
scanf("%lld%lld%lld%lld",&n,&m,&s,&t);
cnt=1;
while(m--)
{
int u,v,c;
scanf("%lld%lld%lld",&u,&v,&c);
add(u,v,c);
add(v,u,0);
}
printf("%lld
",dinic());
return 0;
}
最大流-最小割定理
1、(f) 是 (G) 的一个最大流
2、残余网络 (G_f) 中不存在增广路
3、对于 (G) 的某个割 ([S,T]),有 (|f|=c[S,T])
将 (f) 对应的残余网络 (G_f) 中，构造点集 (S):从源点 (s) 可以到达的顶点的顶点 (v) 组成的集合
$ecause $ 残余网络已经无法找到增广路，意味着无法到达汇点 (t)
( herefore) ([S,V-S]) 是 (s-t) 割
(ecause) 割中都是满流边
( herefore) $$|f|=sum_{uin S}sum_{vin T }f(u,v)-sum_{uin T}sum_{vin S}f(u,v)=sum_{uin S}sum_{vin T }c(u,v)=c[S,T]$$
( herefore f) 是最大流
切割
-
(G=(V,E))的割：([S,V-S])
-
将点集 (V) 划分为 (S) 和 (V-S) 两个部分
-
([S,V-S]) 代表一个边集合
-
割的容量：边集中所有边的容量之和 (c(S,V-S))
-
割的净流量（net flow）:边集中所有边的流量之和定义为 (f(S,V-S))
可以发现，最大流=最小割
如果 (sin S,tin (V-S)),则成为(s-t)割([S,T])
对于一个网络，为了保证没有从 (s) 到 (t) 的路径，要删去的边：
-
(s-t) 割的容量：(c(S，T))
-
(s-t) 割的净流量：(f(S,T))
一个流网络 (G) 中，设任意一个流 (f) ,且 ([S,T]) 为 (G) 的一个割，则通过割的净流量为 (f(S,T)=|f|)
通过割的净流就是网络的可行流
流网络 (G) 中，设任意一个流为 (f) ,任意一个割为([S,T])
(ecause) (S) 中除了源点以外的其他点都流量守恒。
( herefore) (|f|) 为 (S) 的出边的总流量减去 (S) 的入边的总流量
(ecause) (S) 出边的总容量为上限，一定大于等于 (S) 的出边的总流量减去 (S) 的入边的总流量
( herefore) (|f|leq c[S,T])
网络的最大流必定不超过最小割的容量
最大流算法的应用
二分图的匹配问题
P2756 飞行员配对问题
上下界网络流
待补全
费用流算法
基于SPFA的实现
当流网络的边上增加了费用之后，可以在残余网络上沿着最短路增广，反向边的费用就是正向边的值取反，由于流网络中出现负权边，需要用SPFA算法
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<algorithm>
#include<map>
#include<cmath>
#define int long long
using namespace std;
const int N=1e4+1;
const int M=2e6+9;
const int inf=2e10+9;
const int INF = 0x3f3f3f3f;
struct node{
int last;
int c;
int to;
int cost;
}e[M];
int ret=0ll;
int head[N],cnt;
int cur[N],n,m,s,t;
int vis[N],dis[N];
int d[N];
void add(int from,int to,int dis,int cost)
{
e[++cnt].last=head[from];
e[cnt].to=to;
e[cnt].c=dis;
e[cnt].cost=cost;
head[from]=cnt;
}
bool spfa()
{
bool bl = 0;
memset(dis, 127, sizeof(dis));
memcpy(cur, head, sizeof(head));
queue<int> q;
q.push(s);
dis[s] = 0;
vis[s] = 1;
while (!q.empty())
{
int u = q.front();
q.pop();
vis[u] = 0;
for (int i = head[u]; i; i = e[i].last)
{
int v = e[i].to;
if (e[i].c && dis[v] > dis[u] + e[i].cost)
{
dis[v] = dis[u] + e[i].cost;
if (!vis[v]) q.push(v), vis[v] = 1;
if(v == t) bl = 1;
}
}
}
return bl;
}
int dfs(int u,int lim)
{
int flow=0;
if(u==t) return lim;
vis[u]=1;
for(int &i=cur[u];i&&flow<lim;i=e[i].last)
{
int v=e[i].to;
int w=e[i].c;
if(!vis[v]&&w&&dis[v]==dis[u]+e[i].cost)
{
int f=dfs(v,min(w,lim-flow));
if(!f) dis[v] = 0x7fffffff;
ret+=f*e[i].cost;
e[i].c-=f;
e[i^1].c+=f;
flow+=f;
if(flow == lim) break;
}
}
vis[u]=0;
return flow;
}
int dinic()
{
int maxflow=0;
int flow=0;
while(spfa())
while(flow=dfs(s,inf))
maxflow+=flow;
return maxflow;
}
signed main()
{
scanf("%lld%lld%lld%lld",&n,&m,&s,&t);
cnt=1;
while(m--)
{
int x,y,z,cost;
cin>>x>>y>>z>>cost;
add(x,y,z,cost);
add(y,x,0,-cost);
}
int ans=dinic();
cout<<ans<<" "<<ret<<endl;
return 0;
}
典型例题讲解
P4015 运输问题
P4016 负载平衡问题
P2770 航空路线问题
P4014 分配问题
P4013 数字梯形问题
P3358 最长k可重区间集问题
P3357 最长k可重线段集问题
P4012 深海机器人问题
P3356 火星探险问题
P1251 餐巾计划问题
最小割模型的应用
典型例题
UVA1660 有线电视网络
P2762 太空飞行计划问题
最大权闭合图
-
闭合图： 是有向图(G=(V,E)) 的一个点集，且该点集的所有出边都还指向该点集，即闭合图的任意一点的任意后继也一定在闭合图中
-
最大权闭合图：（如给 (G) 中每个点 (v) 分配点权 (w_v)） 点权之和最大的闭合图，即最大化 (sum_{vin V}w_v)
左图中闭合图共有 (9) 个：
(∅), {(5)} , {(2,5)} , {(4,5)} , {(2,4,5)} , {(3,4,5)} ,
{(1,2,4,5)} , {(2,3,4,5)} ,{(1,2,3,4,5)}
最大权闭合图为 {(3,4,5)},权和为 (4)
- 闭合图的性质反映了事件间的必要条件的关系：一个事件的发生，它所需要的所有前提也都要发生。最大权闭合图对应了获益最大或效率最高的事件选择集合。
二分图的最小点权覆盖集与最大点权独立集
待添加