不按24题的顺序，按我做题的顺序

1、飞行员配对方案问题

建个图，跑遍匈牙利，让飞行员给其对应的飞机连一条边

#include 
    
     using namespace std;const int maxn=10000+10;int n,m,e,head[maxn],to[maxn<<1],nxt[maxn<<1],vis[maxn],tot,ans,match[maxn];inline void add(int x,int y){    to[++tot]=y;    nxt[tot]=head[x];    head[x]=tot;}int dfs(int x){    for(int i=head[x];i;i=nxt[i]){        int y=to[i];        if(!vis[y]){            vis[y]=1;            if(!match[y]||dfs(match[y])){                match[y]=x;return 1;            }        }    }    return 0;}int main(){    scanf("%d%d",&n,&m);    int x,y;scanf("%d%d",&x,&y);    while(x!=-1&&y!=-1){        if(x<=n&&y<=n+m) add(x,y);        scanf("%d%d",&x,&y);    }    for(int i=1;i<=n;i++){        memset(vis,0,sizeof(vis));        if(dfs(i)) ans++;    }    if(ans){        printf("%d\n",ans);        for(int i=n+1;i<=m;i++)            if(match[i]) printf("%d %d\n",match[i],i);    }    else printf("No Solution!\n");    return 0;}
    

2、试题库问题

相当于超级源连一条容量为试卷题目总数的边，每张试卷对题目连一条容量为\(1\)的边，题目对超级汇连一条容量为\(1\)的边

方案嘛就找一下残量网络中流量为\(0\)的正向边，然后输出一下它的朝向\(e[i].to-k\)

而且顺带说一句，每一张试卷的题目总数不一定等于它连出的边！

#include 
    
     using namespace std;const int maxn=100000+10;const int inf=0x3f3f3f3f;int k,n,m,s,t,head[maxn],tot=1;int dep[maxn],cur[maxn];struct node{    int to,next,val;}e[maxn];inline void add(int x,int y,int w){    e[++tot].to=y;    e[tot].val=w;    e[tot].next=head[x];    head[x]=tot;}int bfs(int s,int t){    queue
     
       q;    for(int i=0;i<=t;i++)        cur[i]=head[i];    memset(dep,0x7f,sizeof(dep));    dep[s]=0;    q.push(s);    int u,v;    while(!q.empty()){        u=q.front(),q.pop();        for(int i=head[u];i;i=e[i].next){            v=e[i].to;            if(dep[v]>inf&&e[i].val){                dep[v]=dep[u]+1;                q.push(v);            }        }    }    return dep[t]
      
       0){                    printf("%d ",e[i].to-k);                }            }            printf("\n");        }    }    else printf("No Solution\n");    return 0;}
      
     
    

3、最小路径覆盖问题

我用二分图做的，网络流我不知道。二分图建图好建，但是方案难输出

.

方案就是每次找到拆点的\(i'\)，把它映射到\(match[i]\)，开个\(vis\)数组存一下标记

#include 
    
     using namespace std;const int maxn=500+10;int n,m,match[maxn],vis[maxn],ans;vector
     
       G[maxn];int dfs(int x){    int y;    for(int i=0;i
     
    

4、魔术球问题

这题贪心随便水，但是网络流可做

#include 
    
     using namespace std;const int maxn=100000+10;const int inf=0x3f3f3f3f;int n,m=5000,s=0,t=10000,head[maxn],tot=1,cnt;int dep[maxn],cur[maxn],vis[maxn],nxt[maxn],ans[maxn];struct node{    int to,next,val;}e[maxn];inline void add(int x,int y,int w){    e[++tot].to=y;    e[tot].val=w;    e[tot].next=head[x];    head[x]=tot;}int bfs(int s,int t){    queue
     
       q;    for(int i=0;i<=t;i++)        cur[i]=head[i];    memset(dep,-1,sizeof(dep));    dep[s]=0;    q.push(s);    int u,v;    while(!q.empty()){        u=q.front(),q.pop();        for(int i=head[u];i;i=e[i].next){            v=e[i].to;            if(dep[v]==-1&&e[i].val){                dep[v]=dep[u]+1;                q.push(v);            }        }    }    return dep[t]!=-1;}int dfs(int now,int t,int limit){    if(!limit||now==t) return limit;    int flow=0,f,v;    for(int i=cur[now];i;i=e[i].next){        cur[now]=i;v=e[i].to;        if(dep[v]==dep[now]+1&&(f=dfs(v,t,min(limit,e[i].val)))){            flow+=f;            limit-=f;            e[i].val-=f;            e[i^1].val+=f;            if(!limit) break;        }    }    return flow;}int Dinic(){    int maxflow=0;    while(bfs(s,t))        maxflow+=dfs(s,t,inf);    return maxflow;}int main(){    scanf("%d",&n);    int now=0,flow=0;    while(1){        flow++;now++;        for(int i=1;i
      
       n) break;    }    printf("%d\n",--now);    for(int u=1;u<=now;u++){        for(int i=head[u];i;i=e[i].next){            if(!e[i].val){                nxt[u]=e[i].to-m;                break;            }        }    }    for(int i=1;i<=now;i++){        if(!vis[i]){            for(int u=i;u!=-m;u=nxt[u]){                vis[u]=1;                printf("%d ",u);            }            printf("\n");        }    }    return 0;}
      
     
    

5、方格取数问题

奇偶图弄一下，连容量为方格中的数，然后在相邻方格连一条容量为\(inf\)的边

#include 
    
     using namespace std;const int maxn=100000+10;const int inf=1e9;int n,m,s,t;struct Edge{    int to,val,next;}e[maxn<<1];int head[maxn],cur[maxn],deep[maxn],tot=1;int x[4]={0,0,1,-1},y[4]={1,-1,0,0};void add(int x,int y,int w,int flag){    e[++tot].to=y;    e[tot].next=head[x];    head[x]=tot;    if(flag) e[tot].val=w;}int bfs(int s,int t){    queue
     
       q;    for(int i=1;i<=n*m+2;i++)        cur[i]=head[i];    memset(deep,0x7f,sizeof(deep));    deep[s]=0;    q.push(s);    while(!q.empty())    {        int u=q.front();q.pop();        for(int i=head[u];i;i=e[i].next)        {            int y=e[i].to;            if(deep[y]>inf&&e[i].val)            {                deep[y]=deep[u]+1;                q.push(y);            }        }    }    if(deep[t]
      
       n||v<1||v>m) continue;                    add((i-1)*m+j,(u-1)*m+v,inf,1);                    add((u-1)*m+v,(i-1)*m+j,inf,0);                }            }        }    printf("%d\n",sum-Dinic());    return 0;}
      
     
    

6、圆桌问题

比较经典的建图，类似试题库问题，经常结合二分答案+最大流判定（此题不用）

// luogu-judger-enable-o2#include 
    
     using namespace std;const int maxn=100000+10;const int inf=1e9;int n,m,s,t;struct Edge{    int to,val,next;}e[maxn<<1];int head[maxn],cur[maxn],deep[maxn],tot=1;void add(int x,int y,int w,int flag){    e[++tot].to=y;    e[tot].next=head[x];    head[x]=tot;    if(flag) e[tot].val=w;}int bfs(int s,int t){    queue
     
       q;    for(int i=0;i<=n+m+1;i++)        cur[i]=head[i];    memset(deep,0x7f,sizeof(deep));    deep[s]=0;    q.push(s);    while(!q.empty())    {        int u=q.front();q.pop();        for(int i=head[u];i;i=e[i].next)        {            int y=e[i].to;            if(deep[y]>inf&&e[i].val)            {                deep[y]=deep[u]+1;                q.push(y);            }        }    }    if(deep[t]
      
       n&&e[j].to<=n+m&&!e[j].val)                    printf("%d ",e[j].to-n);            printf("\n");        }    }    else printf("0\n");    return 0;}
      
     
    

8、孤岛营救问题

看到题解全是状压+\(bfs\)，我也忍不住打了一个状压+\(bfs\)，一遍过此题

#include 
    
     using namespace std;int n,m,p,k,s;int vis[11][11][1<<11];int mp[11][11][11][11];int now[11][11],nx[4]={1,-1,0,0},ny[4]={0,0,1,-1};struct point{    int x,y,sta,step;};int bfs(){    queue
     
       q;    vis[0][0][0]=1;    q.push((point){1,1,0,0});    point u;int x,y,k;    while(!q.empty()){        u=q.front(),q.pop();        if(u.x==n&&u.y==m) return u.step;        for(k=0;k<4;k++){            x=u.x+nx[k];y=u.y+ny[k];            if(x<1||x>n||y<1||y>m||vis[x][y][u.sta|now[x][y]]) continue;            if(mp[u.x][u.y][x][y]==-1) continue;            if(mp[u.x][u.y][x][y]>0&&!(u.sta&(1<
     
    

9、分配问题

二分图最佳完美匹配，可以类似网络流跑二分图跑两遍费用流，容量全部为\(1\)，涉及超级源超级汇费用为\(0\)，其他情况费用为\(c_{ij}\)

#include 
    
     using namespace std;const int maxn=1000+10;const int maxm=20000+10;const int inf=0x3f3f3f3f;int n,s,t,a[maxn][maxn],head[maxn],tot=1,maxflow,mincost;int pre[maxn],last[maxn],flow[maxn],dis[maxn],vis[maxn];struct node{    int to,next,flow,val;}e[maxm];inline void add(int x,int y,int w,int f){    e[++tot].to=y;    e[tot].flow=w;    e[tot].val=f;    e[tot].next=head[x];    head[x]=tot;}int spfa(){    memset(dis,inf,sizeof(dis));    memset(flow,inf,sizeof(flow));    memset(vis,0,sizeof(vis));    queue
     
       q;    q.push(s);dis[s]=0;vis[s]=1;pre[t]=-1;    int u,v;    while(!q.empty()){        u=q.front(),q.pop();vis[u]=0;        for(int i=head[u];i;i=e[i].next){            v=e[i].to;            if(e[i].flow&&dis[v]>dis[u]+e[i].val){                dis[v]=dis[u]+e[i].val;                flow[v]=min(flow[u],e[i].flow);                pre[v]=u;last[v]=i;                if(!vis[v]){                    vis[v]=1;                    q.push(v);                }            }        }    }    return pre[t]!=-1;}void mcmf(){    int now;    while(spfa()){        now=t;        maxflow+=flow[t];        mincost+=flow[t]*dis[t];        while(now!=s){            e[last[now]].flow-=flow[t];            e[last[now]^1].flow+=flow[t];            now=pre[now];        }    }}int main(){    scanf("%d",&n);    int f;s=0;t=n<<1|1;    for(int i=1;i<=n;i++)        for(int j=1;j<=n;j++) scanf("%d",&a[i][j]);    for(int i=1;i<=n;i++)        for(int j=1;j<=n;j++){            add(i,j+n,1,a[i][j]);add(j+n,i,0,-a[i][j]);        }    for(int i=1;i<=n;i++){        add(s,i,1,0);add(i,s,0,0);        add(i+n,t,1,0);add(t,i+n,0,0);    }    mcmf();    printf("%d\n",mincost);    tot=1;memset(head,0,sizeof(head));    for(int i=1;i<=n;i++)        for(int j=1;j<=n;j++){            add(i,j+n,1,-a[i][j]);add(j+n,i,0,a[i][j]);        }    for(int i=1;i<=n;i++){        add(s,i,1,0);add(i,s,0,0);        add(i+n,t,1,0);add(t,i+n,0,0);    }    maxflow=mincost=0;    mcmf();    printf("%d\n",-mincost);    return 0;}
     
    

10、运输问题

此题是上题的加强版，其他都一样，就是涉及超级源和超级汇的容量是输入的\(a_i\)和\(b_j\)，因为\(\sum_{i=1}^{m}a_i=\sum_{j=1}^{n}b_j\)，所以就是求满流的情况下的最小费用和最大费用，跑两遍费用流

最后就是最大费用边连成负边，最后\(-mincost\)就是最大费用

#include 
    
     using namespace std;const int maxn=200+10;const int maxm=30000+10;const int inf=0x3f3f3f3f;int n,m,s,t,a[maxn],b[maxn],c[maxn][maxn],head[maxn],tot=1,maxflow,mincost;int dis[maxn],vis[maxn],flow[maxn],pre[maxn],last[maxn];struct node{    int to,next,flow,val;}e[maxm];inline int read(){    register int x=0,f=1;char ch=getchar();    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}    return (f==1)?x:-x;}inline void add(int x,int y,int w,int f){    e[++tot].to=y;    e[tot].flow=w;    e[tot].val=f;    e[tot].next=head[x];    head[x]=tot;}int spfa(){    memset(dis,inf,sizeof(dis));    memset(flow,inf,sizeof(flow));    memset(vis,0,sizeof(vis));    queue
     
       q;    q.push(s);dis[s]=0;vis[s]=1;pre[t]=-1;    int u,v;    while(!q.empty()){        u=q.front(),q.pop();vis[u]=0;        for(int i=head[u];i;i=e[i].next){            v=e[i].to;            if(e[i].flow>0&&dis[v]>dis[u]+e[i].val){                dis[v]=dis[u]+e[i].val;                flow[v]=min(flow[u],e[i].flow);                pre[v]=u;last[v]=i;                if(!vis[v]){                    vis[v]=1;                    q.push(v);                }            }        }    }    return pre[t]!=-1;}void mcmf(){    int now;    while(spfa()){        now=t;        maxflow+=flow[t];        mincost+=flow[t]*dis[t];        while(now!=s){            e[last[now]].flow-=flow[t];            e[last[now]^1].flow+=flow[t];            now=pre[now];        }    }}int main(){    n=read(),m=read();    s=0,t=n+m+1;    int f;    for(int i=1;i<=n;i++) a[i]=read();    for(int i=1;i<=m;i++) b[i]=read();    for(int i=1;i<=n;i++)        for(int j=1;j<=m;j++) c[i][j]=read();    for(int i=1;i<=n;i++) add(s,i,a[i],0),add(i,s,0,0);    for(int i=1;i<=m;i++) add(i+n,t,b[i],0),add(t,i+n,0,0);    for(int i=1;i<=n;i++)        for(int j=1;j<=m;j++) add(i,j+n,inf,c[i][j]),add(j+n,i,0,-c[i][j]);    mcmf();    printf("%d\n",mincost);    tot=1;memset(head,0,sizeof(head));    for(int i=1;i<=n;i++) add(s,i,a[i],0),add(i,s,0,0);    for(int i=1;i<=m;i++) add(i+n,t,b[i],0),add(t,i+n,0,0);    for(int i=1;i<=n;i++)        for(int j=1;j<=m;j++) add(i,j+n,inf,-c[i][j]),add(j+n,i,0,c[i][j]);    maxflow=mincost=0;    mcmf();    printf("%d\n",-mincost);    return 0;}