[LOJ 6000]搭配飞行员

link

其实就是一道二分图匹配板子，我们建立$S$,$T$为源点与汇点，然后分别将$S$连向所有正驾驶员，边权为$1$，然后将副驾驶员与$T$相连，边权为$1$，将数据中给出的$(a,b)$,将$a$连向$b$，边权为$1$，然后把反向边记好以后就跑一遍最大流就行

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
inline int read(){
    int f=1,ans=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}
    return f*ans;
}
const int MAXN=50001;
struct node{
    int u,v,w,nex;
}x[MAXN<<1];
int head[MAXN],n,m,cnt,inf=2<<30-1;
void add(int u,int v,int w){
    x[cnt].u=u,x[cnt].v=v,x[cnt].w=w,x[cnt].nex=head[u],head[u]=cnt++;
}
struct NODE{
    int lst,edge;
}pre[MAXN<<1];
int T,S,vis[MAXN];
queue<int> que;
bool bfs(){
    while(!que.empty()) que.pop();
    memset(vis,0,sizeof(vis));
    vis[S]=1;que.push(S);
    while(!que.empty()){
        int xx=que.front();que.pop();
        for(int i=head[xx];i!=-1;i=x[i].nex){
            if(!vis[x[i].v]&&x[i].w){
                vis[x[i].v]=1;
                pre[x[i].v].edge=i,pre[x[i].v].lst=xx;
                if(x[i].v==T) return 1;
                que.push(x[i].v);
            }
        }
    }
    return 0;
}
int ans,ask[MAXN];
int EK(){
    while(bfs()){
        int minn=inf;
        for(int i=T;i!=S;i=pre[i].lst) minn=min(minn,x[pre[i].edge].w);
        ans+=minn;
        for(int i=T;i!=S;i=pre[i].lst){
            x[pre[i].edge].w-=minn;
            x[pre[i].edge^1].w+=minn;
            ask[pre[i].lst]=i;
        }
    }
    return ans;
}int u,v;
int main(){
    memset(head,-1,sizeof(head));
    m=read(),n=read();
    S=0,T=m+1;
    for(int i=1;i<=n;i++) add(S,i,1),add(i,S,0);
    for(int i=n+1;i<=m;i++) add(i,T,1),add(T,i,0);
    while(scanf("%d%d",&u,&v)!=EOF){
        add(u,v,1);
        add(v,u,0);
    }
    printf("%d
",EK());
}