本文共 2857 字，大约阅读时间需要 9 分钟。

背景

在最近的模拟赛当中，我碰到了一题二分图最大权匹配的题，建图比较简单，因为是IOI赛制，所以可以爆OJ，然后呢，打了一发普通的spfa费用流，跑的很慢诶，只拿了70分，都有人AC了呢。那天的讲题，好像说写KM（二分图最大权完美匹配的一种算法）就能过，但是呢，新的东西学还是需要一段时间的，但要订正的话，emm，还是学一学优化的spfa费用流吧，即多路增广一下，事实证明这是能过的。

算法介绍

多路增广非常类似于dinic，然后我不会啊，然后就向高届的大佬请教，大致的算法过程如下

应用

相对于一般的spfa费用流，多路增广尤其适用于边流量特别小的图（这些图一次spfa如果只扩展一条边那么效率将会变得很低下）

实现代码

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        namespace fast_IO{
       const int IN_LEN=10000000,OUT_LEN=10000000;    char ibuf[IN_LEN],obuf[OUT_LEN],*ih=ibuf+IN_LEN,*oh=obuf;    char *lastin=ibuf+IN_LEN;    const char *lastout=ibuf+OUT_LEN-1;    inline char getchar_()    {
           if(ih==lastin)lastin=ibuf+fread(ibuf,1,IN_LEN,stdin),ih=ibuf;        return (*ih++);    }    inline void putchar_(const char x)    {
           if(ih==lastout)fwrite(obuf,1,oh-obuf,stdout),oh=obuf;        *oh++=x;    }    inline void flush(){
   fwrite(obuf, 1, oh - obuf, stdout);}}using namespace fast_IO;//#define getchar() getchar_()//#define putchar(x) putchar_((x))typedef long long LL;#define rg registertemplate 
        
          inline T max(const T a,const T b){ return a>b?a:b;}template 
         
           inline T min(const T a,const T b){ return a
          
           
             inline T abs(const T a){ return a>0?a:-a;}template 
            
              inline void swap(T&a,T&b){ T c=a;a=b;b=c;}template 
             
               inline T gcd(const T a,const T b){ if(a%b==0)return b;return gcd(b,a%b);}template 
              
                inline T square(const T x){ return x*x;};template 
               
                 inline void read(T&x){ char cu=getchar();x=0;bool fla=0; while(!isdigit(cu)){ if(cu=='-')fla=1;cu=getchar();} while(isdigit(cu))x=x*10+cu-'0',cu=getchar(); if(fla)x=-x; }template 
                
                  void printe(const T x){ if(x>=10)printe(x/10); putchar(x%10+'0');}template 
                 
                   inline void print(const T x){ if(x<0)putchar('-'),printe(-x); else printe(x);}const int maxn=5002,maxm=100003;int N,M,S,T,maxflow,mincost;int head[maxn],cur[maxn],nxt[maxm],tow[maxm],vau[maxm],cost[maxm],tmp=1;inline void addb(const int u,const int v,const int w,const int f){ tmp++; nxt[tmp]=head[u]; head[u]=tmp; tow[tmp]=v; vau[tmp]=w; cost[tmp]=f;}int dis[maxn],fr[maxn];int Q[maxn],l,r;bool Hash[maxn];inline int spfa(){ memset(dis,0x7f,sizeof(dis)); dis[S]=0; Hash[S]=1; l=r=0; Q[++r]=S; while(l!=r) { l++;if(l==maxn)l=1; const int u=Q[l]; for(rg int i=head[u];i;i=nxt[i]) { const int v=tow[i]; if(vau[i]&&dis[u]+cost[i]
                  
                   =0x7f7f7f3e)return; } }}int main(){ read(N),read(M),read(S),read(T); for(rg int i=1;i<=M;i++) { int u,v,w,f;read(u),read(v),read(w),read(f); addb(u,v,w,f),addb(v,u,0,-f); } flow(); print(maxflow),putchar(' '),print(mincost); return flush(),0;}
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
    
   

注意事项

使用多路增广网络流使用于一些有性质的图会有很好的效果，但如果只是一般的图的话那么效果就不是那么明显啦（可能是我写的常数比较大吧），所以呢，学多路增广之后，对于普通spfa费用流的熟练掌握还是挺重要的

转载地址：https://blog.csdn.net/zhouyuheng2003/article/details/79133619 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！