很早之前学网络流的时候,就有这么一个想法,要做完网络流24题

后来因为退役就鸽了

现在回来打acm,又重新爬回来填坑

1 飞行员配对方案问题

luogu P2756

一个非常正常的二分图,要求输出匹配

做法也很简单,看反向边是否出现增广路,就表示使用了这个匹配

#include<cstdio>
#include<cstdlib>
#include<iostream>

using namespace std;

#define fr(i,a,b) for(register long long i=a;i<=b;i++)
#define fmin(a,b) ((a)<(b)?(a):(b))
#define travel(i,a,b) for(register long long i=head[a],b=e[i].to;i!=0;i=e[i].next,b=e[i].to)
#define MAXN (2147000000)

struct edge{
    long long to,val,next;
}e[100010];
long long m,n,ans=0,len=1;
long long head[210],d[210],gap[210];

inline long long v_in(){
    char ch=getchar();long long sum=0,f=1;
    while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) sum=(sum<<3)+(sum<<1)+(ch^48),ch=getchar();
    return sum*f;
}

inline void addedge(long long x,long long y,long long z){
    e[++len].to=y;
    e[len].val=z;
    e[len].next=head[x];
    head[x]=len;
}

long long sap(long long u,long long flow){
    if(u==m+2) return flow;
    long long res=flow;
    travel(i,u,v) if(e[i].val&&d[u]==d[v]+1){
        long long t=sap(v,fmin(res,e[i].val));
        e[i].val-=t;
        e[i^1].val+=t;
        res-=t;
        if(!res) return flow;
    }
    if(--gap[d[u]]==0) d[m+1]=m+2;
    gap[++d[u]]++;
    return flow-res;
}

void inpt(){
    n=v_in(),m=v_in();
    fr(i,1,n) addedge(m+1,i,1),addedge(i,m+1,0);
    fr(i,n+1,m) addedge(i,m+2,1),addedge(m+2,i,0);
    //printf("%lld\n",len);
    while(true){
        long long x=v_in(),y=v_in();
        if(x==-1&&y==-1) break;
        addedge(x,y,1);
        addedge(y,x,0);
    }
}

void work(){
    gap[0]=m+2;
    while(d[m+1]<m+2) ans+=sap(m+1,MAXN);
}

void outp(){
    if(ans==0){
        printf("No Solution!\n");
        return;
    }
    printf("%lld\n",ans);
    for(register long long i=2+m+m;i<=len;i+=2) if(e[i^1].val!=0) printf("%lld %lld\n",e[i^1].to,e[i].to);
}

int main(){
    inpt();
    work();
    outp();
    return 0;
}

2 方格取数问题

luogu P2774

比起选数,不如先选上所有数,然后再取消其中一些数的选择

我们需要相邻的点不能选择,所以联想到割,于是:

1.将方格中的点按黑白染色区分,建立源点汇点;

2.源点连向黑点,边权为黑点点权;

3.黑点连向白点,边权为无限大;

4.白点连向汇点,边权为白点点权;

5.求最小割,也就是最大流。

这是最小割的经典题,最大点权覆盖问题(套路++)

#include<cstdio>
#include<cstring>
#include<iostream>

using namespace std;

#define fr(i,a,b) for(register long long i=a;i<=b;i++)
#define MAXN (2147000000)
#define poi(a,b) (((a)-1)*n+(b))
#define fmin(a,b) ((a)<(b)?(a):(b))
#define travel(i,a,b) for(register long long i=head[a],b=e[i].to;i!=0;i=e[i].next,b=e[i].to)

struct edge{
    long long to,val,next;
}e[400010];
long long m,n,st,ed,len=1,ans=0,tot=0;
long long head[10010],gap[10010],d[10010],step[10][5];

inline long long v_in(){
    char ch=getchar();long long sum=0,f=1;
    while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) sum=(sum<<3)+(sum<<1)+(ch^48),ch=getchar();
    return sum*f;
}

inline void addedge(long long x,long long y,long long z){
    e[++len].to=y;
    e[len].val=z;
    e[len].next=head[x];
    head[x]=len;
}

long long sap(long long u,long long flow){
    if(u==ed) return flow;
    long long res=flow;
    travel(i,u,v) if(e[i].val&&d[u]==d[v]+1){
        long long t=sap(v,fmin(res,e[i].val));
        e[i].val-=t;
        e[i^1].val+=t;
        res-=t;
        if(!res) return flow;
    }
    if(--gap[d[u]]<=0) d[st]=m*n+2;
    gap[++d[u]]++;
    return flow-res;
}

void inpt(){
    m=v_in(),n=v_in();
    st=m*n+1,ed=st+1;
    step[1][1]=1; step[1][2]=0;
    step[2][1]=-1; step[2][2]=0;
    step[3][1]=0; step[3][2]=-1;
    step[4][1]=0; step[4][2]=1;
    fr(i,1,m) fr(j,1,n){
        long long w=v_in();
        tot+=w;
        if(((i^j)&1)==0){
            addedge(st,poi(i,j),w);
            addedge(poi(i,j),st,0);
            fr(k,1,4){
                long long x=i+step[k][1],y=j+step[k][2];
                if(x<=m&&x>=1&&y<=n&&y>=1){
                    addedge(poi(i,j),poi(x,y),MAXN);
                    addedge(poi(x,y),poi(i,j),0);
                }
            }
        }
        else{
            addedge(poi(i,j),ed,w);
            addedge(ed,poi(i,j),0);
        }
    }
}

void work(){
    gap[0]=m*n+2;
    long long x=MAXN+MAXN+MAXN;
    while(d[st]<m*n+2) ans+=sap(st,x);
    printf("%lld\n",tot-ans);
}

int main(){
    inpt();
    work();
    return 0;
}

3 太空飞行计划问题

luogu P2762

一道最小割的套路题,最大权闭合子图

这里贴一个大佬的链接

本身应该是一个板子,但是要求记录一组合适方案

我们考虑枚举每一条器材与汇点的边,如果删除后的最大流与本身的最大流的差值为这条边的权值,说明这条边满流,需要使用

// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define re register 
#define f(i,a,b)  for(re int i=(a);i<=(b);i=-(~i))
using namespace std;
const int MAX=2147000000,N=2005,M=2005;
struct node
{
    int u,v,w,next;
}p[2000005],e[2000005];
int head[N],d[N],gap[2000005],val[N],cost[N];
vector<int> req[N];
char c[10010];
bool bo[N],have[N];
int tot=1,s,t,ans,n,m,sum,ulen,flow;
inline void read(int &s)
{
    char c=getchar();int f=1;s=0;
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){s=(s<<3)+(s<<1)+(c^48);c=getchar();}
    s*=f;
}
inline void add(int u,int v,int w)
{
    p[++tot].u=u,p[tot].w=w,p[tot].v=v,p[tot].next=head[u];
    e[tot]=p[tot];
    head[u]=tot;
}
inline void prework()
{
    memset(d,0,sizeof(d));
    memset(gap,0,sizeof(gap));
    f(i,1,tot)p[i]=e[i];
}
int sap(int u,int fl)
{
    if(u==t)return fl;
    int res=fl;
    for(re int i=head[u];i;i=p[i].next)
    {
        int v=p[i].v;
        if(!bo[v]&&p[i].w&&d[u]==d[v]+1)
        {
            int k=sap(v,min(res,p[i].w));
            p[i].w-=k;p[i^1].w+=k;res-=k;
            if(!res)return fl;
        }
    }
    gap[d[u]]--;
    if(!gap[d[u]])d[u]=t+1;
    d[u]++;
    gap[d[u]]++;
    return fl-res;
}
inline void build()
{
    f(i,1,n)
    {
        add(s,i,val[i]),add(i,s,0);
        f(j,0,req[i].size()-1)
        add(i,n+req[i][j],MAX),add(n+req[i][j],i,0);
    }
    f(i,1,m)add(n+i,t,cost[i]),add(t,n+i,0);
}
inline void work(){
    gap[0]=t+1;
    while(d[s]<t+1) flow+=sap(s,MAX);
}
inline void getequip(){
    int fl=0;
    f(i,1,m){
        bo[i+n]=1,fl=0;
        prework();
        gap[0]=t+1;
        while(d[s]<t+1) fl+=sap(s,MAX);
        if(flow-fl==cost[i]) have[i]=1;
        bo[i+n]=0;
    }
}
inline void getexper()
{
    f(i,1,n)
    {
        bool fl=0;
        f(j,0,req[i].size()-1)
        if(!have[req[i][j]])fl=1;
        if(!fl)printf("%d ",i);
    }
}
int main()
{
    int x,y,z,num;
    scanf("%d%d",&n,&m);
    f(i,1,n)
    {
        scanf("%d",&val[i]);
        sum+=val[i];
        memset(c,0,sizeof(c));
        cin.getline(c,10000);
        ulen=0;
        while (sscanf(c+ulen,"%d",&num)==1)
        {
            req[i].push_back(num);
            if (num==0) ulen++;
            else while (num)
            {
                num/=10;
                ulen++;
            }
            ulen++;
        }
    }
    f(i,1,m)scanf("%d",&cost[i]);
    s=0,t=n+m+1;
    build();
    work();
    getequip();
    getexper();
    puts("");
    f(i,1,m)if(have[i])printf("%d ",i);
    puts("");
    ans=sum-flow;
    printf("%d\n",ans);
    return 0;
}

4 负载平衡问题

luogu P4016

一个费用流的简单建图问题

最开始在做这道题的时候,考虑的是最大流没有考虑费用,导致建图建对了反而一直wa

我们可以建这样的图:

1.首先将每个地方拆成两个点,建立源点汇点

2.计算每个地方与目标的差距,如果需要引出则与源点相连,如果需要引入则与汇点相连,流量为差距的绝对值,费用为0

3.既然需要分配,所以我们考虑将相邻的地方,从这个地方的第一个点与相邻地点的两个点都相连,流量无限,费用为1,表示可以调配

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<queue>

using namespace std;

#define fmin(a,b) ((a)<(b)?(a):(b))
#define fr(i,a,b) for(register long long i=a;i<=b;i++)
#define travel(i,a,b) for(register long long i=head[a],b=e[i].to;i!=0;i=e[i].next,b=e[i].to)
#define MAXN (2147000000)

struct edge{
    long long to,val,cost,next;
}e[10010];
queue<long long>q;
long long a[510],head[510],pre[510],last[510],dis[510],flow[510];
long long n,st,ed,sum=0,len=1,mincost=0;
bool vis[510];

inline long long v_in(){
    char ch=getchar();long long sum=0,f=1;
    while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) sum=(sum<<3)+(sum<<1)+(ch^48),ch=getchar();
    return sum*f;
}

inline void addedge(long long x,long long y,long long z,long long w){
    e[++len].to=y;
    e[len].val=z;
    e[len].cost=w;
    e[len].next=head[x];
    head[x]=len;

    e[++len].to=x;
    e[len].val=0;
    e[len].cost=-w;
    e[len].next=head[y];
    head[y]=len;
}

bool SPFA(long long s,long long t){
    memset(dis,0x7f7f7f7f,sizeof(dis));
    memset(flow,0x7f7f7f7f,sizeof(flow));
    memset(vis,0,sizeof(vis));
    q.push(s),vis[s]=1,dis[s]=0,pre[t]=-1;
    while(!q.empty()){
        long long u=q.front(); q.pop();
        vis[u]=0;
        travel(i,u,v) if(e[i].val&&dis[v]>dis[u]+e[i].cost){
            dis[v]=dis[u]+e[i].cost;
            pre[v]=u;
            last[v]=i;
            flow[v]=fmin(flow[u],e[i].val);
            if(!vis[v]){
                vis[v]=1;
                q.push(v);
            }
        }
    }
    return pre[t]!=-1;
}

void inpt(){
    n=v_in();
    st=n+n+1,ed=st+1;
    fr(i,1,n) a[i]=v_in(),sum+=a[i];
    sum/=n;
    fr(i,1,n){
        a[i]-=sum;
        if(a[i]>0) addedge(st,i,a[i],0);
        if(a[i]<0) addedge(n+i,ed,-a[i],0);
    }
    fr(i,2,n-1){
        addedge(i,n+i-1,MAXN,1);
        addedge(i,i-1,MAXN,1);
        addedge(i,n+i+1,MAXN,1);
        addedge(i,i+1,MAXN,1);
    }
    addedge(1,n+2,MAXN,1);
    addedge(1,2,MAXN,1);
    addedge(1,n+n,MAXN,1);
    addedge(1,n,MAXN,1);
    addedge(n,n+1,MAXN,1);
    addedge(n,1,MAXN,1);
    addedge(n,n+n-1,MAXN,1);
    addedge(n,n-1,MAXN,1);
}

void work(){
    while(SPFA(st,ed)){
        long long now=ed;
        mincost+=dis[ed]*flow[ed];
        while(now!=st){
            e[last[now]].val-=flow[ed];
            e[last[now]^1].val+=flow[ed];
            now=pre[now];
        }
    }
    printf("%lld\n",mincost);
}

int main(){
    inpt();
    work();
    return 0;
}

5 餐巾计划问题

luogu P1251

这道题主要是考察建图思想。

首先我们需要考虑将一天拆成早上和晚上

其中晚上的餐巾是可以过夜的,但是并不能在第二天使用,于是前一天晚上向后一天晚上连一条流量无限,费用为0的边

如果送到快洗部,即可以从第i天晚上向第i+m天早上连一条流量无限,费用为f的边

同理,送到慢洗部也应该连边

如果是新购买,可以直接从源点向每天早晨连一条流量无限,费用为p的边

最后源点向每天晚上连一条流量为r[i],费用为0的边,表示每天晚上获得r[i]条脏餐巾

每天早上向汇点连一条流量为r[i],费用为0的边,表示每天早上需要消耗r[i]条新餐巾

最后跑最小费用最大流即可

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<queue>

using namespace std;

#define fr(i,a,b) for(register long long i=a;i<=b;i++)
#define travel(i,a,b) for(register long long i=head[a],b=e[i].to;i!=0;i=e[i].next,b=e[i].to)
#define fmin(a,b) ((a)<(b)?(a):(b))
#define MAXN (214700000)

struct edge{
    long long to,flow,val,next;
}e[100010];
queue<long long>q;
long long N,p,m,f,n,s,len=1,st,ed,mincost=0;
long long r[20010],head[20010],pre[20010],last[20010],flow[20010],dis[20010];
bool vis[20010];

inline long long v_in(){
    char ch=getchar();long long sum=0,f=1;
    while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) sum=(sum<<3)+(sum<<1)+(ch^48),ch=getchar();
    return sum*f;
}

inline void addedge(long long u,long long v,long long w,long long z){
    e[++len].to=v;
    e[len].flow=w;
    e[len].val=z;
    e[len].next=head[u];
    head[u]=len;

    e[++len].to=u;
    e[len].flow=0;
    e[len].val=-z;
    e[len].next=head[v];
    head[v]=len;
}

bool SPFA(long long s,long long t){
    memset(dis,0x7f,sizeof(dis));
    memset(flow,0x7f,sizeof(flow));
    memset(vis,0,sizeof(vis));
    q.push(s),vis[s]=1,dis[s]=0,pre[t]=-1;
    while(!q.empty()){
        long long u=q.front(); q.pop();
        vis[u]=0;
        travel(i,u,v) if(e[i].flow&&dis[v]>dis[u]+e[i].val){
            dis[v]=dis[u]+e[i].val;
            pre[v]=u;
            last[v]=i;
            flow[v]=fmin(flow[u],e[i].flow);
            if(!vis[v]){
                vis[v]=1;
                q.push(v);
            }
        }
    }
    return pre[t]!=-1;
}

void inpt(){
    N=v_in();
    fr(i,1,N) r[i]=v_in();
    p=v_in(),m=v_in(),f=v_in(),n=v_in(),s=v_in();
    //build
    st=N*2+1,ed=st+1;
    fr(i,1,N){
        addedge(st,i+N,r[i],0);
        addedge(i,ed,r[i],0);
    }
    fr(i,1,N){
        if(i+1<=N) addedge(i+N,i+N+1,MAXN,0);
        if(i+m<=N) addedge(i+N,i+m,MAXN,f);
        if(i+n<=N) addedge(i+N,i+n,MAXN,s);
        addedge(st,i,MAXN,p);
    }
}

void work(){
    while(SPFA(st,ed)){
        long long now=ed;
        mincost+=flow[ed]*dis[ed];
        while(now!=st){
            e[last[now]].flow-=flow[ed];
            e[last[now]^1].flow+=flow[ed];
            now=pre[now];
        }
    }
    printf("%lld\n",mincost);
}

int main(){
    inpt();
    work();
    return 0;
}

6.试题库问题

luogu P2763

很简单的一道二分图问题

只不过类型流向汇点时,边权变成题中所给的要求数量即可

输出时只需要判断试题连向类型的边有没有增广路即可

#include<cstdio>
#include<cstdlib>
#include<iostream>

using namespace std;

#define fr(i,a,b) for(register long long i=a;i<=b;i++)
#define travel(i,a,b) for(register long long i=head[a],b=e[i].to;i!=0;i=e[i].next,b=e[i].to)
#define fmin(a,b) ((a)<(b)?(a):(b))
#define MAXN (100000000)

struct edge{
    long long to,val,next;
}e[100010];
long long n,m,st,ed,len=1,sum=0;
long long head[2010],d[2010],gap[2010];

inline long long v_in(){
    char ch=getchar();long long sum=0,f=1;
    while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) sum=(sum<<3)+(sum<<1)+(ch^48),ch=getchar();
    return sum*f;
}

inline void addedge(long long x,long long y,long long z){
    e[++len].to=y;
    e[len].val=z;
    e[len].next=head[x];
    head[x]=len;

    e[++len].to=x;
    e[len].val=0;
    e[len].next=head[y];
    head[y]=len;
}

long long sap(long long u,long long flow){
    if(u==ed) return flow;
    long long res=flow,t;
    travel(i,u,v) if(e[i].val&&d[u]==d[v]+1){
        t=sap(v,fmin(e[i].val,res));
        e[i].val-=t;
        e[i^1].val+=t;
        res-=t;
        if(!res) return flow;
    }
    if(--gap[d[u]]<=0) d[st]=m+n+2;
    gap[++d[u]]++;
    return flow-res;
}

void inpt(){
    n=v_in(),m=v_in();
    st=m+n+1,ed=st+1;
    fr(i,1,n){
        long long x=v_in();
        sum+=x;
        addedge(m+i,ed,x);
    }
    fr(i,1,m){
        addedge(st,i,1);
        long long opt=v_in();
        fr(j,1,opt){
            long long x=v_in();
            addedge(i,m+x,1);
        }
    }
}

void work(){
    long long ans=0;
    gap[0]=m+n+2;
    while(d[st]<m+n+2) ans+=sap(st,MAXN);
    if(ans!=sum){
        printf("No Solution!\n");
        return;
    }
    //travel(i,ed,v) printf("%lld %lld\n",v,e[i].val);
    fr(u,m+1,m+n){
        printf("%lld: ",u-m);
        travel(i,u,v) if(v<=m&&v>=1&&e[i].val!=0) printf("%lld ",v);
        printf("\n");
    }
}

int main(){
    inpt();
    work();
    return 0;
}

7 最小路径覆盖问题

luogu P2764

这是一道板子题

ans就是用n减去二分图匹配的最大值

我们假设本身由n条路径,每条路径覆盖图中不重复的每一个点

我们可以二分图来合并这些路径

如果两个在图中相连,我们就可以将这两条路径合并

最后得到的最大流,就是能够合并路径的最大数量,于是我们用总路径数n减去最大流,得到的就是最小路径覆盖

关于记录路径

我们可以考虑每一个点,如果他没有被流入,说明他是起点

然后从这个点开始依次寻找它流向的点,即合并的路径,依次输出即可

#include<cstdio>
#include<cstdlib>
#include<iostream>

using namespace std;

#define fr(i,a,b) for(register long long i=a;i<=b;i++)
#define travel(i,a,b) for(register long long i=head[a],b=e[i].to;i!=0;i=e[i].next,b=e[i].to)
#define fmin(a,b) ((a)<(b)?(a):(b))
#define MAXN (100000000)

struct edge{
    long long to,val,next;
}e[100010];
long long n,m,st,ed,len=1;
long long head[2010],d[2010],gap[2010];

inline long long v_in(){
    char ch=getchar();long long sum=0,f=1;
    while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) sum=(sum<<3)+(sum<<1)+(ch^48),ch=getchar();
    return sum*f;
}

inline void addedge(long long x,long long y,long long z){
    e[++len].to=y;
    e[len].val=z;
    e[len].next=head[x];
    head[x]=len;

    e[++len].to=x;
    e[len].val=0;
    e[len].next=head[y];
    head[y]=len;
}

long long sap(long long u,long long flow){
    if(u==ed) return flow;
    long long res=flow,t;
    travel(i,u,v) if(e[i].val&&d[u]==d[v]+1){
        t=sap(v,fmin(e[i].val,res));
        e[i].val-=t;
        e[i^1].val+=t;
        res-=t;
        if(!res) return flow;
    }
    if(--gap[d[u]]<=0) d[st]=m+n+2;
    gap[++d[u]]++;
    return flow-res;
}

void inpt(){
    n=v_in(),m=v_in();
    st=n+n+1,ed=st+1;
    fr(i,1,n) addedge(st,i,1),addedge(n+i,ed,1);
    fr(i,1,m){
        long long u=v_in(),v=v_in();
        addedge(u,n+v,1);
    }
}

void work(){
    long long ans=0;
    gap[0]=m+n+2;
    while(d[st]<m+n+2) ans+=sap(st,MAXN);
    fr(u,n+1,n+n){
        bool mark=false;
        travel(i,u,v) if(v<=n&&v>=1&&e[i].val){
            mark=true;
            break;
        }
        if(!mark){
            long long now=u-n;
            while(1){
                printf("%lld ",now);
                long long nxt=0;
                travel(i,now,v){
                    //printf(" *%lld ",v);
                    if(v>=n+1&&v<=n+n&&e[i].val==0){
                        nxt=v-n;
                        break;
                    }
                }
                if(!nxt) break;
                now=nxt;
            }
            printf("\n");
        }
    }
    printf("%lld\n",n-ans);
}

int main(){
    inpt();
    work();
    return 0;
}