网络流模板-白红宇

网络流模板

阅读量：4970 次

发布时间：2019-06-12

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

Dinic

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define maxn 10500#define inf 1e9using namespace std;int n,m,tot=1,head[maxn],S,T,t1,t2,t3;int d[maxn],flag[maxn],cur[maxn],ans,fl[maxn];long long anse,ansv;struct node{ int v,nex,cap;}e[200005];void Q(){ tot=1; memset(head,0,sizeof head);}void lj(int t1,int t2,int t3){ tot++;e[tot].v=t2,e[tot].cap=t3;e[tot].nex=head[t1];head[t1]=tot;}bool BFS(){ for(int i=1;i<=Max;i++)d[i]=inf,flag[i]=0; queue
           
            q;q.push(S);d[S]=0; while(!q.empty()){ int x=q.front();q.pop();cur[x]=head[x]; for(int i=head[x];i;i=e[i].nex){ if(d[e[i].v]>d[x]+1&&e[i].cap){ d[e[i].v]=d[x]+1; if(!flag[e[i].v]){ flag[e[i].v]=1;q.push(e[i].v); } } } flag[x]=0; } return d[T]!=inf;}int lian(int k,int a){ //cout<
            
             <<' '<
             <
              
               0){ flow+=f;a-=f; e[i].cap-=f;e[i^1].cap+=f; if(!a)break; } } return flow;}int main(){ scanf("%d%d%d%d",&n,&m,&S,&T); for(int i=1;i<=m;i++){ scanf("%d%d%d",&t1,&t2,&t3); lj(t1,t2,t3);lj(t2,t1,0); } ans=0; while(BFS())ans+=lian(S,inf); cout<
               
                <

ISAP（现在不会了）

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #define maxn 10005#define maxm 100005#define inf 1e9using namespace std;int n,m,S,T,now[maxn],head[maxn],t1,t2,t3,tot=1;int flag[maxn],d[maxn],pre[maxn],num[maxn],ans;struct node{ int nex,v,cap;}e[maxm*2];void lj(int t1,int t2,int t3){ tot++;e[tot].v=t2,e[tot].cap=t3;e[tot].nex=head[t1];head[t1]=tot;}void BFS(){ queue
             
              q; flag[T]=1;q.push(T); while(!q.empty()){ int x=q.front();q.pop(); ///printf("orz %d\n",x); for(int i=head[x];i;i=e[i].nex){ if(!flag[e[i].v]&&e[i^1].cap>0){ flag[e[i].v]=1; d[e[i].v]=d[x]+1; q.push(e[i].v); } } }}int get(){ int flow=inf; for(int i=T;;i=e[pre[i]].v) { if(i==S)break; flow=min(e[pre[i]^1].cap,flow); } for(int i=T;;i=e[pre[i]].v){ if(i==S)break; e[pre[i]].cap+=flow; e[pre[i]^1].cap-=flow; } return flow;}void lian(){ BFS(); memset(num,0,sizeof(num)); //for(int i=1;i<=n;i++)cout<
              
               <<' ';cout<
               
                0){ //cout<
                <<' '<
                 
                  <<'\n'; mi=min(d[e[i].v],mi); } } //cout<
                  
                   >n>>m>>S>>T; for(int i=1;i<=m;i++) { scanf("%d%d%d",&t1,&t2,&t3); lj(t1,t2,t3);lj(t2,t1,0); } lian(); printf("%d\n",ans); return 0;}

费用流（单路增广）

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #define maxn 5002#define inf 1e9using namespace std;int n,m,S,T,head[maxn],tot=1,t1,t2,t3,t4,fl;int d[maxn],flag[maxn],ans,cur[maxn];struct node{ int v,nex,cap,w;}e[100002];void lj(int t1,int t2,int t3,int t4){ tot++;e[tot].v=t2;e[tot].cap=t3;e[tot].w=t4;e[tot].nex=head[t1];head[t1]=tot;}bool spfa(){ for(int i=1;i<=n;i++)d[i]=inf,flag[i]=0; queue
             
              q;q.push(S);d[S]=0; while(!q.empty()){ int x=q.front();q.pop(); for(int i=head[x];i;i=e[i].nex){ if(e[i].cap>0&&d[e[i].v]>d[x]+e[i].w){ d[e[i].v]=d[x]+e[i].w; if(!flag[e[i].v])flag[e[i].v]=1,q.push(e[i].v); } } flag[x]=0; } return d[T]!=inf;}int dfs(int k,int a){ flag[k]=1; if(k==T||a==0)return a; int f,flow=0; for(int &i=cur[k];i;i=e[i].nex){ if(d[e[i].v]==d[k]+e[i].w&&e[i].cap&&!flag[e[i].v]){//attention!!! f=dfs(e[i].v,min(e[i].cap,a)); flow+=f;a-=f;e[i].cap-=f;e[i^1].cap+=f; ans+=f*e[i].w; if(a==0)break; } } return flow;}int main(){ cin>>n>>m>>S>>T; for(int i=1;i<=m;i++){ scanf("%d%d%d%d",&t1,&t2,&t3,&t4); lj(t1,t2,t3,t4);lj(t2,t1,0,-t4); } while(spfa()){ flag[T]=1; while(flag[T]){ memset(flag,0,sizeof(flag)); for(int i=1;i<=n;i++)cur[i]=head[i]; fl+=dfs(S,inf); } } cout<
              
               <<' '<
               
                <

费用流（zkw）

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #define maxn 5002#define inf 1e9using namespace std;int n,m,S,T,head[maxn],tot=1,t1,t2,t3,t4,fl;int d[maxn],flag[maxn],ans,cur[maxn];struct node{ int v,nex,cap,w;}e[100002];void lj(int t1,int t2,int t3,int t4){ tot++;e[tot].v=t2;e[tot].cap=t3;e[tot].w=t4;e[tot].nex=head[t1];head[t1]=tot;}bool spfa(){ for(int i=1;i<=n;i++)d[i]=inf,flag[i]=0; queue
             
              q;q.push(S);d[S]=0; while(!q.empty()){ int x=q.front();q.pop(); for(int i=head[x];i;i=e[i].nex){ if(e[i].cap>0&&d[e[i].v]>d[x]+e[i].w){ d[e[i].v]=d[x]+e[i].w; if(!flag[e[i].v])flag[e[i].v]=1,q.push(e[i].v); } } flag[x]=0; } return d[T]!=inf;}int dfs(int k,int a){ flag[k]=1; if(k==T||a==0)return a; int f,flow=0; for(int &i=cur[k];i;i=e[i].nex){ if(d[e[i].v]==d[k]+e[i].w&&e[i].cap&&!flag[e[i].v]){//attention!!! f=dfs(e[i].v,min(e[i].cap,a)); flow+=f;a-=f;e[i].cap-=f;e[i^1].cap+=f; ans+=f*e[i].w; if(a==0)break; } } return flow;}int main(){ cin>>n>>m>>S>>T; for(int i=1;i<=m;i++){ scanf("%d%d%d%d",&t1,&t2,&t3,&t4); lj(t1,t2,t3,t4);lj(t2,t1,0,-t4); } while(spfa()){ flag[T]=1; while(flag[T]){ memset(flag,0,sizeof(flag)); for(int i=1;i<=n;i++)cur[i]=head[i]; fl+=dfs(S,inf); } } cout<
              
               <<' '<
               
                <