题解 P4722 【【模板】最大流 加强版 / 预流推进】
cosmicAC
2018-10-01 20:53:54
## 参考文献：[http://kczno1.blog.uoj.ac/blog/3375](http://kczno1.blog.uoj.ac/blog/3375)
两个多月前就AC此题的我现在(2018.10)才来发题解，主要是因为太懒了。记得当时我翻遍了提交记录，只有我一个人写的Dinic。
**[我的博客](https://www.luogu.org/blog/474D/)**
首先，对于Dinic有一个可能没多少人知道的**改进复杂度的**优化（**伸缩操作**），可以将其加速到$O(nmlog{C})$，这里的C是最大的容量。具体做法很简单:
1. 将所有边按照其容量二进制下的位数从大到小排序，位数相同的合并成一段。
2. 顺序枚举每一段，在残量网络中加入这一段所有的边，跑一次(普通的)Dinic，将新增广的流量加入答案
具体复杂度为什么是对的呢?参见算导的思考题26-5，和那个差不多。（~~其实我也不会证。~~）
但是观察这一题的数据范围，这个复杂度仍不足以通过。所以需要进一步的优化。充分发挥Dinic玄学复杂度的优势，有一个玄学的方法：先不加反向边，跑一次上面的算法；再一次性地把所有反向边加入残量网络，重跑一遍。程序的效率得到了大幅提升。
目前（即10月1日），下面的程序在本站和LOJ上都能通过。
```cpp
// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define maxn 1300
#define maxm 120010
using namespace std;
struct edge{
int u,v,cap;
}e[maxm];
struct Dinic{
int tp,s,t,dis[maxn],cur[maxn],que[maxn];
vector<edge>e;vector<int>v[maxn];
void AddEdge(int x,int y,int flw){
e.push_back(edge{x,y,flw});
e.push_back(edge{y,x,0});
v[x].push_back(e.size()-2);
//v[y].push_back(e.size()-1);
}
int bfs(){
memset(dis,0x3f,sizeof dis);
int l=1,r=1;que[1]=s;dis[s]=0;
while(l<=r){
int p=que[l++],to;
for(int i:v[p])if(e[i].cap && dis[to=e[i].v]>1e9)
dis[to]=dis[p]+1,que[++r]=to;
}
return dis[t]<1e9;
}
int dfs(int p,int a){
if(p==t || !a)return a;
int sf=0,flw;
for(int &i=cur[p],to;i<(int)v[p].size();++i){
edge &E=e[v[p][i]];
if(dis[to=E.v]==dis[p]+1 && (flw=dfs(to,min(a,E.cap)))){
E.cap-=flw;e[v[p][i]^1].cap+=flw;
a-=flw;sf+=flw;
if(!a)break;
}
}
return sf;
}
int dinic(int s,int t,int tp=1){
this->s=s;this->t=t;this->tp=tp;
int flw=0;
while(bfs()){
memset(cur,0,sizeof cur);
flw+=dfs(s,INT_MAX);
}
return flw;
}
}sol;
int n,m,i,s,t,ans;
int main(){
scanf("%d%d%d%d",&n,&m,&s,&t);
for(i=0;i<m;i++)scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].cap);
sort(e,e+m,[](edge a,edge b){return a.cap>b.cap;});
for(int tp:{0,1})for(int p=1<<30,i=0;p;p/=2){
while(i<m && e[i].cap>=p){
if(tp)sol.v[e[i].v].push_back(i*2+1);
else sol.AddEdge(e[i].u,e[i].v,e[i].cap);
i++;
}
ans+=sol.dinic(s,t,tp);
}
printf("%d\n",ans);
return 0;
}
```
最后，希望毒瘤出题人能够进一步的加强数据。