前言

摆王兴致冲冲地跑到我们机房来对我说跟你讲一个黑科技。。。

Dinic的神奇优化

Dinic优化

我们发现如果Dinic不建反向边会跑的飞起（当然Wa是必然的）

所以考虑在加反向边的基础上优化.

首先我们记录网络中最大的一个流量，设它为Min，然后：

把所有小于Min的边都加入网络中

最大流+=Dinic()

Min /= 2

到1
然后在Dinic时不走反向边（但是值要改变），最后在可以走反向边的情况下再来一次

注意bfs的一些操作,如果不当会溢出...

代码实现

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             using namespace std;#define ll long long#define re register#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)#define int llinline int gi(){ int f=1,sum=0;char ch=getchar(); while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();} return f*sum;}const int N=500010,M=2000010,Inf=1e10+10;int n,m,s,t,ans,dep[N],cur[N];struct node{ int u,v,c;}E[M];vector
             
              front[N];vector
              
               e;void Add(int u,int v,int c){ e.push_back((node){u,v,c}); e.push_back((node){v,u,0}); front[u].push_back(e.size()-2);}bool cmp(node a,node b){ return a.c>b.c;}queue
               
                Q;bool bfs(){ memset(dep,127,sizeof(dep)); Q.push(s);dep[s]=0; while(!Q.empty()) { int u=Q.front();Q.pop(); for(int i=0;i
                
                 1e9 && e[id].c) { dep[v]=dep[u]+1; Q.push(v); } } } return dep[t]<1e9;}int dfs(int u,int flow) {// printf("%lld %lld\n",u,flow); if(!flow || u==t)return flow; int F=0; for(int &i=cur[u];i
                 
                  >=1) { while(now
                  
                   =p) { if(!type)Add(E[now].u,E[now].v,E[now].c); else front[E[now].v].push_back(now*2+1); now++; } ans+=Dinic(); } } printf("%lld\n",ans); return 0;}