Luogup2756 pilot pairing scheme problem (maximum flow)

Subject portal

A typical bipartite graph matching problem
Foreign pilots as X Ministry , British pilots as Y Ministry
The source points to X Partial edge , Capacity of 1
Y The local convergence point is connected to the edge , Capacity of 1
X Department and Y Between the two sides , Capacity of 1

crazy WA It's not just because of the scheme output
I use an array record here （ Foreign pilot , British pilots ） The number of the side
The default value of array is 0
dinic Then judge whether the capacity of the edge is 0
Note that you need to determine whether the number of records in the array is valid （ Is it the default value ）

Tip

Be careful bfs and dfs When , You need to determine whether the current edge has capacity

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
using namespace std;

const int INF=0x33333333;
const int N=105;
int mp[N][N];
int st[N],tot=-1;
struct node{
    
    int x,y,v,nxt;
};
node way[N*N];
int n,m,s,t;

void addway(int u,int w,int z) {
    
    tot++;
    way[tot].x=u; 
    way[tot].y=w;
    way[tot].v=z;
    way[tot].nxt=st[u];
    st[u]=tot;
}

queue<int> q;
int cur[N];
int deep[N];
int bfs() {
    
    memset(deep,-1,sizeof(deep));
    for (int i=0;i<=n+1;++i) cur[i]=st[i];
    q.push(s);
    deep[s]=1;
    while (!q.empty()) {
    
        int r=q.front();
        q.pop();
        for (int i=st[r];i!=-1;i=way[i].nxt) {
    
            int y=way[i].y;
            if (way[i].v && deep[y]==-1) {
       //way[i].v!=0
                q.push(y);
                deep[y]=deep[r]+1;
            }
        }
    }
    return deep[t]!=-1;
}

int dfs(int now,int t,int limit) {
    
    if (now==t || !limit) return limit;
    int f,flow=0;
    for (int i=cur[now];i!=-1;i=way[i].nxt) {
    
        cur[now]=i;
        if (way[i].v && deep[way[i].y]==deep[now]+1 && (f=dfs(way[i].y,t,min(limit,way[i].v)))) {
    
            way[i].v-=f;
            way[i^1].v+=f;
            limit-=f;
            flow+=f;
            if (!limit) break;
        }
    }
    return flow;
}

int dinic() {
    
    int ans=0;
    while (bfs()) {
    
        ans+=dfs(s,t,INF);
    }
    return ans;
}

int main()
{
    
    memset(st,-1,sizeof(st));
    scanf("%d%d",&m,&n);
    s=0;
    t=n+1;
    for (int i=1;i<=n;i++) {
    
        if (i<=m) {
    
            addway(s,i,1);
            addway(i,s,0);
        }
        else {
    
            addway(i,t,1);
            addway(t,i,0);
        }
    }
    int x,y;
    scanf("%d%d",&x,&y);
    while (x!=-1 && y!=-1) {
    
        addway(x,y,1);
        mp[x][y]=tot;
        addway(y,x,0);
        scanf("%d%d",&x,&y);
    }
    printf("%d\n",dinic());
    for (int i=1;i<=m;++i) {
    
        for (int j=m+1;j<=n;++j) {
    
            if (mp[i][j] && way[mp[i][j]].v == 0) {
    
                printf("%d %d\n",i,j);
            }    
        }
    }
    return 0;
}