首页 > 代码库 > 网络流算法与建模总结
网络流算法与建模总结
【算法】
1.最大流
(1) 容量限制:对于∀u,v∈V ，要求 f (u,v) ≤ c(u,v)。
(2) 反对称性:对于∀u,v∈V ，要求 f (u,v) = − f (v,u)。
(3) 流量平衡:对于∀u∈V −{s,t}，要求∑f(u,v)=0。
dinic
- 根据残量网络计算层次图。
- 在层次图中使用DFS沿阻塞流(不考虑反向弧时的极大流 层次图中的)进行增广直到不存在增广路
- 重复以上步骤直到无法增广
int cur[N];int vis[N],d[N],q[N],head,tail;bool bfs(){ memset(vis,0,sizeof(vis)); memset(d,0,sizeof(d)); head=tail=1; q[tail++]=s;d[s]=0;vis[s]=1; while(head!=tail){ int u=q[head++]; for(int i=h[u];i;i=e[i].ne){ int v=e[i].v; if(!vis[v]&&e[i].c>e[i].f){ vis[v]=1;d[v]=d[u]+1; q[tail++]=v; if(v==t) return 1; } } } return 0;}int dfs(int u,int a){ if(u==t||a==0) return a; int flow=0,f; for(int &i=cur[u];i;i=e[i].ne){ int v=e[i].v; if(d[v]==d[u]+1&&(f=dfs(v,min(a,e[i].c-e[i].f)))>0){ flow+=f; e[i].f+=f; e[((i-1)^1)+1].f-=f; a-=f; if(a==0) break; } } return flow;}int dinic(){ int flow=0; while(bfs()){ for(int i=s;i<=t;i++) cur[i]=h[i]; flow+=dfs(s,INF); } return flow;}
2.最小割
最大流的对偶问题
流网络G =(V,E)的割(cut)[S,T]将点集V划分为S和T(T =V −S)两个部分，
使得源s∈S且汇t∈T。符号[S,T]代表一个边集合{ u,v | u,v ∈E,u∈S,v∈T}。
穿过割 [S,T]的净流(net flow)定义为 f (S,T)，割[S,T]的容量(capacity)定义为c(S,T)，一般 记为c[S,T]。
一个网络的最小割(minimum cut)也就是该网络中容量最小的割。
增广路算法结束时，所有还有流量(从s走)的点组成S，没有流量的点组成T
最大流的流量就是最小割的容量
3.最小费用最大流
(1)spfa费用流
用spfa找最短路来增广
保存pre[i]和pos[i]分别是最短路中的父节点和入边
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>using namespace std;typedef long long ll;const int N=5005,M=5e4+5,INF=1e9;int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1; c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘; c=getchar();} return x*f;}int n,m,s,t,u,v,w,c;struct edge{ int v,ne,c,f,w;}e[M<<1];int cnt,h[N];inline void ins(int u,int v,int c,int w){ cnt++; e[cnt].v=v;e[cnt].c=c;e[cnt].f=0;e[cnt].w=w; e[cnt].ne=h[u];h[u]=cnt; cnt++; e[cnt].v=u;e[cnt].c=0;e[cnt].f=0;e[cnt].w=-w; e[cnt].ne=h[v];h[v]=cnt;}int d[N],pre[N],pos[N],q[N],head=1,tail=1,inq[N];inline void lop(int &x){if(x==N) x=1;else if(x==0) x=N-1;}bool spfa(){ memset(d,127,sizeof(d)); d[s]=0;pre[t]=-1; head=tail=1; memset(inq,0,sizeof(inq)); q[tail++]=s;inq[s]=1; while(head!=tail){ int u=q[head++];lop(head);inq[u]=0; for(int i=h[u];i;i=e[i].ne){ int v=e[i].v,w=e[i].w; if(d[v]>d[u]+w&&e[i].c>e[i].f){ d[v]=d[u]+w; pre[v]=u; pos[v]=i; if(!inq[v]){ if(d[v]<d[q[head]]) head--,lop(head),q[head]=v; else q[tail++]=v,lop(tail); inq[v]=1; } } } } return pre[t]==-1?0:1;}void mcmf(){ ll flow=0,cost=0; while(spfa()){ int f=INF; for(int i=t;i!=s;i=pre[i]) f=min(f,e[pos[i]].c-e[pos[i]].f); flow+=f; cost+=f*d[t]; for(int i=t;i!=s;i=pre[i]){ e[pos[i]].f+=f; e[((pos[i]-1)^1)+1].f-=f; } } printf("%lld %lld",flow,cost);}int main(int argc, const char * argv[]) { n=read();m=read();s=read();t=read(); for(int i=1;i<=m;i++){ u=read();v=read();c=read();w=read(); ins(u,v,c,w); } mcmf(); return 0;}
(2)zkw费用流
http://www.artofproblemsolving.com/community/c1368h1020435
【建模】
1.公平分配问题
把X分配给Y，一个X有两个Y可选，让分配到最多的最少
二分图模型，X和Y构成二分图
二分最多最少值mid
s--1-->X--1-->Y--mid-->t
看maxflow==|X|
2.最大闭合子图
定义一个有向图G = (V,E)的闭合图(closure)10是该有向图的一个点集，且该点集的所 有出边都还指向该点集。即闭合图内的任意点的任意后继也一定在闭合图中。
在原图点集的基础上增加源s和汇t;
将原图每条有向边 u,v ∈E替换为容量为c(u,v)=∞的有向边u,v ∈EN;
增加连接源s到原图每个正权点v(wv >0)的有向边s,v ∈EN，容量为c(s,v)=wv;
增加连接原图每个负权点v(wv <0)到汇t的有向边v,t ∈EN，容量为c(v,t)=−wv
(这样下来两个边权都是正数)
s--点权-->正权点----INF----负权点--|点权|-->t
胡波涛论文中有详细证明
我们也可以简单的思考最小割，要么(1)把s-->正u割了，要么(2)把负v-->t割了
(1)相当于不选择这个u，他的后继就没必要选了，同时损失wu
(2)相当于选择了u，同时选择了他的后继v，所以损失wv
3.二分图最大匹配
s--1-->X--1-->Y--1-->t
4.最小路径覆盖问题
G 的最小路径覆盖是G 的所含路径条数最少的路径覆盖。
有点逆向思考的感觉
最差情况所有的点都是一条路径
两个点连起来的话就少一条路径一个点
拆成入点X和出点Y，构成二分图，ans=n-最大匹配数
5.
网络流算法与建模总结