【初步整理】网络流相关

【求最大流】

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int inf=1000000000;
const int maxn=200000;
int Laxt[maxn],Next[maxn],To[maxn],Cap[maxn],cnt=1;
int dis[maxn],nd[maxn],n,m;
int add(int u,int v,int c)
{
    Next[++cnt]=Laxt[u];
    Laxt[u]=cnt;
    To[cnt]=v;
    Cap[cnt]=c;
    
    Next[++cnt]=Laxt[v];
    Laxt[v]=cnt;
    To[cnt]=u;
    Cap[cnt]=0;
}
int sap(int u,int flow)
{
    if(u==n||flow==0) return flow;
    int delta=0,tmp;
    for(int i=Laxt[u];i;i=Next[i]){
        int v=To[i];
        if(dis[v]+1==dis[u]&&Cap[i]>0){
            tmp=sap(v,min(Cap[i],flow-delta));
            delta+=tmp;
            Cap[i]-=tmp;
            Cap[i^1]+=tmp;
            if(flow==delta||dis[1]>=n) return delta;
        }
    }
    nd[dis[u]]--;
    if(nd[dis[u]]==0) dis[1]=n;
    nd[++dis[u]]++;
    return delta;
}
int main()
{
    int i,j,c,ans=0,u,v;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++){
        scanf("%d%d%d",&u,&v,&c);
        add(u,v,c);
    }
    nd[0]=n;
    while(dis[1]<n){
        ans+=sap(1,inf);
    }
    printf("%d
",ans);
}
View Code

【求割：】

 

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int inf=1000000000;
const int maxn=200000;
int Laxt[maxn],Next[maxn],To[maxn],Cap[maxn],cnt=1;
int dis[maxn],nd[maxn],n,m;
int S[maxn],num;
int add(int u,int v,int c)
{
    Next[++cnt]=Laxt[u];
    Laxt[u]=cnt;
    To[cnt]=v;
    Cap[cnt]=c;
    
    Next[++cnt]=Laxt[v];
    Laxt[v]=cnt;
    To[cnt]=u;
    Cap[cnt]=0;
}
void dfs(int u)
{
    num++;
     S[u]=1;
     for(int i=Laxt[u];i;i=Next[i]){
            if(Cap[i]&&!S[To[i]])dfs(To[i]);
     }
}
int sap(int u,int flow)
{
    if(u==n||flow==0) return flow;
    int delta=0,tmp;
    for(int i=Laxt[u];i;i=Next[i]){
        int v=To[i];
        if(dis[v]+1==dis[u]&&Cap[i]>0){
            tmp=sap(v,min(Cap[i],flow-delta));
            delta+=tmp;
            Cap[i]-=tmp;
            Cap[i^1]+=tmp;
            if(flow==delta||dis[1]>=n) return delta;
        }
    }
    nd[dis[u]]--;
    if(nd[dis[u]]==0) dis[1]=n;
    nd[++dis[u]]++;
    return delta;
}
int main()
{
    int i,j,c,ans=0,u,v;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++){
        scanf("%d%d%d",&u,&v,&c);
        add(u,v,c);
    }
    nd[0]=n;
    while(dis[1]<n){
        ans+=sap(1,inf);
    }  
    dfs(1);
    printf("%d %d
",ans,num);
    for(i=1;i<=n;i++)
       if(S[i]) printf("%d ",i);
    return 0;
}
View Code

题型整理：之前有过题目小结，但是很零散：网络流

1，求最大流。如飞行员配对，方格取数。

2，求割。如狼羊分割模型。

3，费用流。

4，二分图多重匹配。

5，最小点覆盖，最大独立集。

6，最小路径覆盖。

7，最大权闭合子图。

8，缩点。

9，拆点。

10，有上下界的最大流。

11，其他：最小费用环。

慢慢整理

HDU3549：基础模板1

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<memory.h>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn=2010;
const int inf=0x7fffffff;
int vd[maxn],dis[maxn];
int Laxt[maxn],Next[maxn],To[maxn],V[maxn];
int n,m,cnt,ans;
void _update()
{
    memset(Laxt,0,sizeof(Laxt));
    memset(vd,0,sizeof(vd));
    memset(dis,0,sizeof(dis));
    memset(V,0,sizeof(V));
    cnt=2;
    ans=0;
}
void _add(int u,int v,int c)
{
    Next[cnt]=Laxt[u];
    Laxt[u]=cnt;
    To[cnt]=v;
    V[cnt++]=c;
    Next[cnt]=Laxt[v];
    Laxt[v]=cnt;
    To[cnt]=u;
    V[cnt++]=0;
}
int _sap(int u,int flow)
{
    int tmp,delta=0;
    if(flow==0||u==n) return flow;
    for(int i=Laxt[u];i;i=Next[i])
    {
        if(dis[To[i]]+1==dis[u]&&V[i]>0){
            tmp=_sap(To[i],min(flow-delta,V[i]));
            V[i]-=tmp;
            V[i^1]+=tmp;
            delta+=tmp;
            if(delta==flow||dis[1]>=n) return delta;
        }
    }
    vd[dis[u]]--;
    if(vd[dis[u]]==0) dis[1]=n+1;
    vd[++dis[u]]++;
    return delta;
}
int main()
{
     int T,t,i,j,x,y,z;
     cin>>T;
     for(t=1;t<=T;t++){
         scanf("%d%d",&n,&m);
         _update();
         for(i=1;i<=m;i++){
             scanf("%d%d%d",&x,&y,&z);
             _add(x,y,z);
         }
         while(dis[1]<n+1){
                ans+=_sap(1,inf);
         }
         printf("Case %d: %d
",t,ans);        
     }
     return 0;
}
View Code

HDU1532：基础模板：2

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<memory.h>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn=2010;
const int inf=0x7fffffff;
int vd[maxn],dis[maxn];
int Laxt[maxn],Next[maxn],To[maxn],V[maxn];
int n,m,cnt,ans;
void _update()
{
    memset(Laxt,0,sizeof(Laxt));
    memset(vd,0,sizeof(vd));
    memset(dis,0,sizeof(dis));
    memset(V,0,sizeof(V));
    cnt=2;
    ans=0;
}
void _add(int u,int v,int c)
{
    Next[cnt]=Laxt[u];
    Laxt[u]=cnt;
    To[cnt]=v;
    V[cnt++]=c;
    Next[cnt]=Laxt[v];
    Laxt[v]=cnt;
    To[cnt]=u;
    V[cnt++]=0;
}
int _sap(int u,int flow)
{
    int tmp,delta=0;
    if(flow==0||u==n) return flow;
    for(int i=Laxt[u];i;i=Next[i])
    {
        if(dis[To[i]]+1==dis[u]&&V[i]>0){
            tmp=_sap(To[i],min(flow-delta,V[i]));
            V[i]-=tmp;
            V[i^1]+=tmp;
            delta+=tmp;
            if(delta==flow||dis[1]>=n) return delta;
        }
    }
    vd[dis[u]]--;
    if(vd[dis[u]]==0) dis[1]=n;
    vd[++dis[u]]++;
    return delta;
}
int main()
{
     int T,t,i,j,x,y,z;
      while(~scanf("%d%d",&m,&n)){
         _update();
         for(i=1;i<=m;i++){
             scanf("%d%d%d",&x,&y,&z);
             _add(x,y,z);
         }
         while(dis[1]<n){
                ans+=_sap(1,inf);
         }
         printf("%d
",ans);        
     }
     return 0;
}
View Code

HDU3605：状态压缩，好题

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<memory.h>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int maxm=401000;
const int inf=0x7fffffff;
int vd[maxm],dis[maxm];
int Laxt[maxm],Next[maxm],To[maxm],V[maxm];
int n,m,cnt,ans,s,t;
int a[maxm],c[maxm];
void _update()
{
    memset(Laxt,0,sizeof(Laxt));
    memset(dis,0,sizeof(dis));
    memset(vd,0,sizeof(vd));
    memset(a,0,sizeof(a));
    memset(c,0,sizeof(c));
    cnt=2;
    ans=0;
}
void _add(int u,int v,int c)
{
    Next[cnt]=Laxt[u];
    Laxt[u]=cnt;
    To[cnt]=v;
    V[cnt++]=c;
    Next[cnt]=Laxt[v];
    Laxt[v]=cnt;
    To[cnt]=u;
    V[cnt++]=0;
}
int _sap(int u,int flow)
{
    int tmp,delta=0;
    if(flow==0||u==t) return flow;
    for(int i=Laxt[u];i;i=Next[i])
    {
        if(dis[To[i]]+1==dis[u]&&V[i]>0){
            tmp=_sap(To[i],min(flow-delta,V[i]));
            V[i]-=tmp;
            V[i^1]+=tmp;
            delta+=tmp;
            if(delta==flow||dis[s]>t) return delta;
        }
    }
    vd[dis[u]]--;
    if(vd[dis[u]]==0) dis[s]=t+1;
    vd[++dis[u]]++;
    return delta;
}
int main()
{
    int n,m,i,j,Max,x;
    while(~scanf("%d%d",&n,&m))
    {
         _update();
         Max=0;
         for(i=1;i<=n;i++){
            int tmp=0;
            for(j=1;j<=m;j++) {
               scanf("%d",&x);
               tmp=tmp*2+x;
            }
            if(tmp>Max) Max=tmp;
            a[tmp]++;
         }
         s=0;t=Max+m+1;
         for(i=1;i<=m;i++) scanf("%d",&c[i]);
         for(i=1;i<=Max;i++){
                if(a[i]>0) {
                    _add(0,i,a[i]);
                    int k=m,p=i;
                    while(k&&p){
                        int tmp=p%2;
                        p/=2;
                        if(tmp>0) _add(i,Max+k,inf);
                        k--;
                    }
                }
         }
         for(i=1;i<=m;i++) _add(Max+i,t,c[i]);
         while(dis[s]<=t) {
                ans+=_sap(s,inf);
         }
         if(ans==n) printf("YES
");
         else printf("NO
");
    }
    return 0;
}
View Code

HDU3572：任务分配1

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<memory.h>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn=510000;
const int inf=0x7fffffff;
int vd[maxn],dis[maxn];
int Laxt[maxn],Next[maxn],To[maxn],V[maxn];
int n,m,cnt,ans,s,t,num;
void _update()
{
    memset(Laxt,0,sizeof(Laxt));
    memset(vd,0,sizeof(vd));
    memset(dis,0,sizeof(dis));
    memset(V,0,sizeof(V));
    cnt=2;
    ans=0;
    num=0;
}
void _add(int u,int v,int c)
{
    Next[cnt]=Laxt[u];
    Laxt[u]=cnt;
    To[cnt]=v;
    V[cnt++]=c;
    Next[cnt]=Laxt[v];
    Laxt[v]=cnt;
    To[cnt]=u;
    V[cnt++]=0;
}
int _sap(int u,int flow)
{
    int tmp,delta=0;
    if(flow==0||u==t) return flow;
    for(int i=Laxt[u];i;i=Next[i])
    {
        if(dis[To[i]]+1==dis[u]&&V[i]>0){
            tmp=_sap(To[i],min(flow-delta,V[i]));
            V[i]-=tmp;
            V[i^1]+=tmp;
            delta+=tmp;
            if(delta==flow||dis[s]>t) return delta;
        }
    }
    vd[dis[u]]--;
    if(vd[dis[u]]==0) dis[s]=t+1;
    vd[++dis[u]]++;
    return delta;
}
int main()
{
      int T,i,j,x,y,z,Case=0;
      scanf("%d",&T);
      while(T--){
         scanf("%d%d",&n,&m);
         s=0;t=500+n+1;
         _update();
         for(i=1;i<=n;i++){
             scanf("%d%d%d",&z,&x,&y);
             num+=z;
             for(j=x;j<=y;j++)
               _add(j,500+i,1);
             _add(500+i,t,z);
         }
         for(i=1;i<=500;i++)
          _add(s,i,m);
         while(dis[s]<=t){
                ans+=_sap(s,inf);
         }
         if(ans==num) printf("Case %d: Yes
",++Case);
         else printf("Case %d: No
",++Case);    
         printf("
");    
      }
      return 0;
}
View Code

HDU2883：任务分配2

HDU3081：男女配对

HDU3046：狼羊割

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<memory.h>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn=401000;
const int inf=0x7fffffff;
int vd[maxn],dis[maxn];
int Laxt[maxn],Next[maxn],To[maxn],V[maxn];
int n,m,cnt,ans,s,t;
int num[220][220];
int x[4]={0,1,0,-1};
int y[4]={1,0,-1,0};
void _update()
{
    memset(Laxt,0,sizeof(Laxt));
    memset(vd,0,sizeof(vd));
    memset(dis,0,sizeof(dis));
    memset(V,0,sizeof(V));
    cnt=2;
    ans=0;
}
void _add(int u,int v,int c)
{
    Next[cnt]=Laxt[u];
    Laxt[u]=cnt;
    To[cnt]=v;
    V[cnt++]=c;
    Next[cnt]=Laxt[v];
    Laxt[v]=cnt;
    To[cnt]=u;
    V[cnt++]=0;
}
int _sap(int u,int flow)
{
    int tmp,delta=0;
    if(flow==0||u==t) return flow;
    for(int i=Laxt[u];i;i=Next[i])
    {
        if(dis[To[i]]+1==dis[u]&&V[i]>0){
            tmp=_sap(To[i],min(flow-delta,V[i]));
            V[i]-=tmp;
            V[i^1]+=tmp;
            delta+=tmp;
            if(delta==flow||dis[s]>t) return delta;
        }
    }
    vd[dis[u]]--;
    if(vd[dis[u]]==0) dis[s]=t+1;
    vd[++dis[u]]++;
    return delta;
}
int main()
{
    int n,m,i,j,Case=0;
    while(~scanf("%d%d",&n,&m))
    {
         s=0;t=n*m+1;
         _update();
         for(i=1;i<=n;i++)
          for(j=1;j<=m;j++)
            scanf("%d",&num[i][j]);
         for(i=1;i<=n;i++)
          for(j=1;j<=m;j++){    
                for(int k=0;k<4;k++)
                if(i+x[k]>=1&&j+y[k]>=1&&i+x[k]<=n&&j+y[k]<=m){
                    if(num[i][j]==0&&num[i+x[k]][j+y[k]]==0)
                      _add((i-1)*m+j,(i+x[k]-1)*m+j+y[k],1);
                    else if(num[i][j]!=num[i+x[k]][j+y[k]])
                      _add((i-1)*m+j,(i+x[k]-1)*m+j+y[k],1);
                }
                if(num[i][j]==1) _add(s,(i-1)*m+j,4);
                if(num[i][j]==2) _add((i-1)*m+j,t,4);
          }
         while(dis[s]<t+1){
                ans+=_sap(s,inf);
         }
         printf("Case %d:
%d
",++Case,ans);        
    }
    return 0;
}
View Code

HDU2732:拆点：

HDU3917：最大闭合权值

HDU3468：最大流+最短路

HDU3861：缩点+最小路径覆盖

#include<cstdio>
#include<cstring>
#include<stack>
#include<cstdlib> 
#include<queue>
#include<memory.h>
#include<algorithm>
#include<vector>
#include<iostream>
using namespace std;
const int maxn=5010;
vector<int>G[maxn];
vector<int>G2[maxn];
vector<int>S;
vector<int>Map[maxn];
int scc[maxn],vis[maxn],n,m,scc_cnt,ans;
int link[maxn];
void _update(){
    for(int i=1;i<=n;i++) G[i].clear();
    for(int i=1;i<=n;i++) G2[i].clear();
    memset(link,0,sizeof(link));
    memset(vis,0,sizeof(vis));
    memset(scc,0,sizeof(scc));
    S.clear();
    ans=scc_cnt=0;
}
void _dfs1(int v){
    if(vis[v]) return ;
    vis[v]=1;
    int L=G[v].size();
    for(int i=0;i<L;i++)_dfs1(G[v][i]);
    S.push_back(v);
    return ;
}
void _dfs2(int v){
    if(scc[v]) return ;
    scc[v]=scc_cnt;
    int L=G2[v].size();
    for(int i=0;i<L;i++) _dfs2(G2[v][i]);
}
void _kosaraju()
{
    for(int i=1;i<=n;i++)_dfs1(i);
    for(int i=n-1;i>=0;i--) {
        if(!scc[S[i]]) {
            scc_cnt++;
            Map[scc_cnt].clear(); 
            _dfs2(S[i]);
         }
    }
    for(int i=1;i<=n;i++)
    {
        int L=G[i].size();
        for(int j=0;j<L;j++){
            if(scc[i]!=scc[G[i][j]]){
               Map[scc[i]].push_back(scc[G[i][j]]);
            }
        }
    }
} 
bool _find(int v){
    int L=Map[v].size();
    for(int i=0;i<L;i++)
    {
        if(!vis[Map[v][i]]){
            vis[Map[v][i]]=1;
            if(!link[Map[v][i]]||_find(link[Map[v][i]])){
                link[Map[v][i]]=v;
                return true;
            }
        }
    }
    return false;
}
int main()
{
    int T,i,j,u,v;
    scanf("%d",&T);
    while(T--){
        _update();
        scanf("%d%d",&n,&m);
        for(i=1;i<=m;i++){
            scanf("%d%d",&u,&v);
            G[u].push_back(v);
            G2[v].push_back(u);
        }
        _kosaraju();
        for(i=1;i<=scc_cnt;i++){
            memset(vis,0,sizeof(vis));
            if(_find(i)) {
              ans++;
            }
        }
        printf("%d
",scc_cnt-ans);//以Map图位对象，不是n 
    }
    return 0;
}
View Code

HDU3488：我也不知道叫什么覆盖

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<memory.h>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=310;
const int inf=0x7ffffff;
int map[maxn][maxn];
int vis1[maxn],vis2[maxn];
int ex1[maxn],ex2[maxn];
int lack[maxn];
int link[maxn];
int ans,n;
int x1[maxn],x2[maxn],y[maxn],y2[maxn];
int Abs(int v){
    if(v<0) v=-v;
    return v;
}
bool _bfs(int v)
{
    vis1[v]=true;
    for(int i=1;i<=n;i++){
        if(!vis2[i]){
            int tmp=ex1[v]+ex2[i]-map[v][i];
            if(tmp==0){
              vis2[i]=true;
              if(!link[i]||_bfs(link[i])){
                 link[i]=v;
                 return true;
              }
            }
            else if(tmp<lack[i]) lack[i]=tmp;
        }
    }
    return false;
}
void _KM()
{
    int t,i,j;
    memset(link,0,sizeof(link));
    memset(ex2,0,sizeof(ex2));
    for(i=1;i<=n;i++){
        ex1[i]=map[i][1];
        for(j=2;j<=n;j++)
         if(ex1[i]<map[i][j]) ex1[i]=map[i][j];
    }
    for(t=1;t<=n;t++){
        for(i=1;i<=n;i++) lack[i]=inf;//思考：为什么在这里？ 
        while(true){ 
            memset(vis1,0,sizeof(vis1));
            memset(vis2,0,sizeof(vis2));
            if(_bfs(t))  break;
            int gap=inf;
            for(i=1;i<=n;i++)
             if(!vis2[i]&&lack[i]<gap) gap=lack[i];
            for(i=1;i<=n;i++) if(vis1[i]) ex1[i]-=gap;
            for(i=1;i<=n;i++) if(vis2[i]) ex2[i]+=gap;
            for(i=1;i<=n;i++) if(!vis2[i])lack[i]-=gap;
        }
    }
    ans=0;
    for(i=1;i<=n;i++)
       ans-=map[link[i]][i];
    ans=ans;
    printf("%d
",ans);
}
int main()
{
    int i,j,m,T,u,v,w;
    scanf("%d",&T);
    while(T--){
      scanf("%d%d",&n,&m);
      for(i=1;i<=n;i++)
       for(j=1;j<=n;j++) map[i][j]=100000000;
       for(i=1;i<=m;i++){
            scanf("%d%d%d",&u,&v,&w);
            if(w<map[u][v]) map[u][v]=w;
       }
       for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)map[i][j]=-map[i][j];
        _KM();
    }
    return 0;
}
View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/hua-dong/p/7834447.html