最大流与Dijkstra做费用流

### 0x00网络流简介 　　网络流$G=(V, E)$是一个有向图,其中每条边$(u, v)$均有一个非负的容量值,记为$c(u, v)\geq0$.如果$(u, v)\notin E$则可以规定$c(u, v)=0$.网络流中有两个特殊的顶点,即源点$S$和汇点$T$,源点可以提供无限的流量,而汇点可以接受无限的流量. 　　与网络流相关的一个概念是流.设$S$为网络的源点,$T$为汇点，那么$G$的流是一个函数$f:V×V →R$,满足以下性质: 　　容量限制：$\forall u,v∈V$，满足$f(u, v) \leq c(u, v)$; 　　反对称性：$\forall u,v∈V$，满足$f(u, v) = - f(v, u)$; 　　流守恒性：$\forall u∈V-{S, T}$，满足$\sum_{v∈V}f(u,v)=0$。 　　流$f$的值定义为 $$|f|=\sum_{v\in V}f(s,v)$$ 　　而最大流就是值最大的流. 　　可以形象地理解为:源点是一个水库,汇点是一个用水量无限的用户,其它点是中转站,而边就是连接三者的水管.一个流就是一种合法的输水方案(每条水管运送水量在其容量之内,除了源点不会莫名其妙地出现水),它的值就是用户接受到的水量,而最大流就是用户接受水量最大的输水方案. 　　残留网络是由可以容纳更多流的边组成的,即如果$G$中的一条边没有满流,那么它就是残留网络$G_f$中的一条边. 　　一条增广路则是指$G_f$中从$S$到$T$的一条路径. ### 0x01最大流算法:以Dinic算法为例 >以下定义: >$w[i]$为边$i$的边权 >$w[i][j]$为连接$i,j$的边的边权 >$c[i]$为边$i$的费用 >$dis[i]$为起点到点$i$的距离 >$S$为源点 >$T$为汇点 Dinic算法大致步骤: 1.用BFS给图标号,每个点的标号为到源点的最近距离(只走剩余容量大于0的边). 2.若BFS无法到达汇点则算法结束. 3.DFS一遍找出一条从源点到汇点的增广路,DFS时只走标号比当前点大1的点. 4.若没有这样的路径则返回1,否则将此路计入答案,并更新反向边,重复3. 反向边的概念: 假设有这样一个图(边上的数字代表其容量)  现在有一条2到5的路径  对于路径上每一条边(u,v),建立一条(v,u),容量为经过(u,v)的流量的边(图中绿色边)  假设又有一条6到1的边  那么最终的图是这样的(每条边上:(容量,流量))  例子:  BFS标号  DFS  更新反向边  由于无路可走,再BFS并DFS  更新反向边  无路可走,退出 最终:  PS:每条边上(容量,流量) [Code(P3376)](https://paste.ubuntu.com/p/ppCHBXGKFm/) ``` #define out(i,a,now) for(int i=a.be[now],to=a.v[i];i;i=a.ne[i],to=a.v[i]) #define fo(i,a,b) for(i=a;i<=b;i++) struct adj_list { LL be[maxn],ne[maxm<<2],v[maxm<<2],w[maxm<<2],cnt; void init() { qk(be); cnt=1; } void add(LL x,LL y,LL z) { v[++cnt]=y; ne[cnt]=be[x]; w[cnt]=z; be[x]=cnt; } }v; LL bfs()//标号 { queue<LL> q; q.push(t); qk(id); id[t]=1; while (!q.empty()) { LL now=q.front(); q.pop(); if (now==s) break; out(i,v,now) if (v.w[i^1] && !id[to]) { id[to]=id[now]+1; q.push(to); } } return id[s];//判断是否有可行流 } LL dfs(LL now,LL flow)//寻找可行流 { if (now==t) return flow; LL miflow; out(i,v,now) { LL wei=v.w[i]; if (wei && id[to]==id[now]-1) { miflow=dfs(to,min(flow,wei)); if (miflow) { v.w[i]-=miflow; v.w[i^1]+=miflow;//增加反向边流量 return miflow; } } } return 0; } LL dinic() { LL res=0; while (bfs()) { LL temp; while (temp=dfs(s,LLONG_MAX>>1)) res+=temp; } return res; } int main() { scanf("%lld%lld%lld%lld",&n,&m,&s,&t); LL i; LL x,y,z; v.init(); fo(i,1,m) { scanf("%lld%lld%lld",&x,&y,&z); v.add(x,y,z); v.add(y,x,0); } LL ans=dinic(); printf("%lld",ans); } ``` ### 0x02最小费用最大流算法 　　现在你需要为流经一条边$i$的单位流量支付费用$c[i]$,其实只需将最大流算法中的DFS改为求最短路,找到一条从源点到汇点每条边费用之和最小的路并更新答案. 　　鉴于现在SPFA人人喊打,以下给出一种使用dijkstra算法的方法. 　　由于费用可能为负数,普通的dijkstra算法无法实现.因此我们考虑对原图做一次SPFA求出源点到每个点的最短路,之后我们为每个点$i$赋点权$h[i]$为$dis[i]$,并视每条连接$u,v$的边$i$的边权$w'[i]$为$w[i]+h[u]-h[v]$,由于对于任意两点$u,v$,有$h[u]-h[v]>=w[u][v]$,所以$w'[i]>=0$,这样一来新图上的$dis'[i]$就等于$dis[i]+h[S]-h[i]$(对于路径上除起点和终点以外的点$i$,其入边的$-h[i]$与出边的$+h[i]$抵消),由于每次跑最短路时$h[i]$都是不变的,所以求出了$dis'[i]$也就求出了$dis[i]$($dis[i]=dis'[i]-h[S]+h[i]$,其实很显然$h[S]=0$) 　　但是跑完之后需要加入反向边,原来的$h[i]$可能会不适用,所以我们需要更新$h[i]$ 对于最短路上每一条连接$(u,v)$的边,显然有$$dis'[u]+w'[u][v]=dis'[v]$$ 从而 $$dis'[u]+h[u]-h[v]+w[u][v]=dis'[v]$$ $$(dis'[u]+h[u])-(dis'[v]+h[v])+w[u][v]=0$$ $$∵w[u][v]=-w[v][u]$$ $$∴(dis'[v]+h[v])-(dis'[u]+h[u])+w[v][u]=0$$ 所以我们只要对于每个点$i$将$h[i]$加上$dis'[i]$即可. 由于 $dis'[i]+h[i]=dis[i]+h[S]-h[i]+h[i]=dis[i]+h[S]$ h[S]又是一个常量(就是$0$) 所以$h[i]$还是一开始我们所希望的$dis[i]$,对于每个点$i$将$h[i]$加上$dis'[i]$不会破坏每条边边权不为负的特性. [Code(P3381)](https://paste.ubuntu.com/p/wj5cbZwSZK/) ``` #define out(i,a,now) for(int i=a.be[now],to=a.v[i];~i;i=a.ne[i],to=a.v[i]) #define fo(i,a,b) for(i=a;i<=b;i++) struct adj_list { LL be[maxn],ne[maxm<<4],v[maxm<<4],w[maxm<<4],c[maxm<<4],cnt; void init() { memset(be,-1,sizeof(be)); cnt=0; } void add(LL pre,LL nxt,LL wei,LL cost) { v[cnt]=nxt; ne[cnt]=be[pre]; be[pre]=cnt; w[cnt]=wei; c[cnt]=cost; ++cnt; } }; struct NetWork { adj_list v; LL dis[maxn],h[maxn],pre_node[maxn],pre_edge[maxn],inque[maxn]; void SPFA(LL be,LL en) { queue<LL> q; qk(inque); LL i; fo(i,1,n) h[i]=LLONG_MAX>>1; h[be]=0; inque[be]=1; q.push(be); while (!q.empty()) { LL now=q.front(); q.pop(); out(i,v,now) if (h[now]+v.c[i]<h[to] && v.w[i]) { h[to]=h[now]+v.c[i]; if (!inque[to]) { q.push(to); inque[to]=1; } } inque[now]=0; } } void MCMF(LL s,LL t,LL &flow,LL &cost) { flow=cost=0; SPFA(s,t);//用一次SPFA更新h数组 while (1) { pre_node[s]=pre_edge[s]=-1;//开始堆优化dijkstra算法 LL i; fo(i,1,n) dis[i]=LLONG_MAX>>1; dis[s]=0; priority_queue<Pair,vector<Pair>,greater<Pair> > pq; pq.push(mp(0,s)); while(!pq.empty()) { Pair now=pq.top(); pq.pop(); if (now.first!=dis[now.second]) continue; if (now.second==t) break; out(i,v,now.second) { LL len=v.c[i]+h[now.second]-h[to]; if (v.w[i] && dis[now.second]+len<dis[to]) { dis[to]=dis[now.second]+len; pq.push(mp(dis[to],to)); pre_node[to]=now.second;//记录从哪个点来 pre_edge[to]=i;//记录从哪条边来 } } } if (dis[t]>=(LLONG_MAX>>1)) break; LL miflow=LLONG_MAX>>1; for(i=t;i!=s;i=pre_node[i]) cmin(miflow,v.w[pre_edge[i]]);//找到路径上流量最小值 for(i=t;~i;i=pre_node[i]) { v.w[pre_edge[i]]-=miflow; v.w[pre_edge[i]^1]+=miflow;//更新反向边 } flow+=miflow; cost+=miflow*(h[t]+dis[t]); fo(i,1,n) h[i]=min(h[i]+dis[i],LLONG_MAX>>1);//更新h数组 } } void sol() { v.init(); LL i,x,y,z,w; scanf("%lld%lld%lld%lld",&n,&m,&s,&t); fo(i,1,m) { scanf("%lld%lld%lld%lld",&x,&y,&z,&w); v.add(x,y,z,w); v.add(y,x,0,-w); } LL flow,cost; MCMF(s,t,flow,cost); printf("%lld %lld",flow,cost); } }solver; int main() { solver.sol(); return 0; } ``` ### 0x03最小割最大流定理 　　$G$的一个割把点集$V$分为两部分,其中源点S属于其中一部分,汇点T属于另外一部分.割是$G$的边集$E$的一个子集,每条边的两个端点分别属于不同的点集.割的容量定义为割的每条边的容量和,最小割就是容量最小的一个割. 　　例子: 　　 　　黄色的边就是一个割 　　介绍一下网络流中最重要的定理之一------最小割最大流定理: 　　如果$f$是$G$中一个流,则以下条件是等价的: 　　1.$f$是$G$的一个最大流 　　2.残留网络$G_f$不包含增广路 　　3.存在一个割,$|f|$等于其容量 　　那么如何借此求出最小割呢?我们看可以先求出最大流,以S为起点在残留网络上DFS,搜索到的点就是包含S的一部分,剩余的则是另一部分,而最小割即是连接两部分的所有边. ### 0x04典型例题 1.飞行员配对方案问题([P2756](https://www.luogu.org/problemnew/show/P2756)) 　　一个二分图最大匹配问题,源点向所有外籍飞行员连容量为1的边,外籍飞行员向可以配对的英国飞行员连容量为1的边,英国飞行员向汇点连容量为1的边,网络最大流即是答案,若外籍飞行员连向英国飞行员的边满流,说明这一对被选中. 　　[Code](https://paste.ubuntu.com/p/DdRK4xwbff/) 2.太空飞行计划问题([P2762](https://www.luogu.org/problemnew/show/P2762)) 　　一个最大权闭合图问题,详细说明可以见胡伯涛的[《最小割模型在信息学竞赛中的应用》](https://github.com/sserdoubleh/ACM/blob/master/knowledge/%E7%AE%97%E6%B3%95%E5%90%88%E9%9B%86%E4%B9%8B%E3%80%8A%E6%9C%80%E5%B0%8F%E5%89%B2%E6%A8%A1%E5%9E%8B%E5%9C%A8%E4%BF%A1%E6%81%AF%E5%AD%A6%E7%AB%9E%E8%B5%9B%E4%B8%AD%E7%9A%84%E5%BA%94%E7%94%A8%E3%80%8B.pdf). 　　简要说一下方法:源点向实验连容量为利润的边,实验向所需器材连容量为无穷大的边,器材向汇点连容量为花费的边,所有实验利润之和减去网络最小割的容量即是答案,方案可以按照上文方法输出. 　　[Code](https://paste.ubuntu.com/p/mCmY9pYCHj/) 3.最小路径覆盖问题([P2764](https://www.luogu.org/problemnew/show/P2764)) 　　寻找最小路径条数等价于为尽可能多的点找到后继,于是就可以用一种类似于二分图匹配的方法求解.将点$i$拆为$i_1,i_2$,源点向所有$i_1$连容量为1的边,所有$i_2$向汇点连容量为1的边,若原图上有边$(u,v)$,则$u_1$向$v_2$连容量为1的边.答案为总点数减去网络最大流(网络最大流就是找到了后继的点数),若$u_1$向$v_2$的边满流,说明路径上$v$是$u$的后继. 　　[Code](https://paste.ubuntu.com/p/kbbXyPwpty/)