Aimee

可以用网络流解决

建超级源点与超级汇点，源点与所有的外籍飞行员相连，容量为1（顶多选一人一次）

超级汇点同理，容量还是1，而飞行员之间的点就可以使大于等于1的任意数

顶多只有1的流量

最后所有漫流的边即为方案

方案书就是最大流

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
std::queue <int> q;
using namespace std;
const int maxn=20001;
int head[maxn];
int inf=(1<<29);
struct b{
    int to;
    int ne;
    int f;
    int v;
}ed[maxn];
int p=0;
void add(int f,int t,int v){
    ed[++p].ne=head[f];ed[p].to=t;ed[p].v=v;head[f]=p;ed[p].f=f;
    ed[++p].ne=head[t];ed[p].to=f;ed[p].v=0;head[t]=p;
}
int le[maxn];
int fr[maxn];
int Aimee;
int n,m;
int znx;
int x,y;
bool bfs(){
    memset(le,-1,sizeof(le));
    while(!q.empty())
        q.pop();
    q.push(0);
    le[0]=0;
    fr[0]=head[0];
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=ed[i].ne){
            int v=ed[i].to;
            if(ed[i].v&&le[v]==-1){
                q.push(v);le[v]=le[u]+1;
                fr[v]=head[v];
                if(v==n+1){
                    return 1;
                }
            }
        }
    }
    return 0;
}
long long dfs(int now,int task){
    if(now==n+1) return task;
    long long znx=0;
    for(int i=fr[now];i&&znx<task;i=ed[i].ne){
        fr[now]=i;
        int v=ed[i].to;
        if(le[v]==le[now]+1&&ed[i].v){
            long long jdn=dfs(v,min((long long)ed[i].v,task-znx));
            if(!jdn) le[v]=-1;
            ed[i].v-=jdn;
            ed[i^1].v+=jdn;
            znx+=jdn;
        }
    }
    return znx;
}
long long dinic(){
    while(bfs()){
        while(znx=dfs(0,inf)){
            Aimee+=znx;
        }
    }
    return Aimee;
}
int cnt;
int main(){
    scanf("%d%d",&m,&n);
    while(1){
        scanf("%d%d",&x,&y);
        if(x==-1)
        break;
        add(x,y,1);
        cnt++;
    }
    for(int i=1;i<=m;++i){
        add(0,i,1);
    }
    for(int i=m+1;i<=n;++i){
        add(i,n+1,1);
    }
    cout<<dinic()<<endl;
    for(int i=1;i<=cnt*2;i+=2){
        if(ed[i].v==0){
            printf("%d %dn",ed[i].f,ed[i].to);
        }
    }
    return 0;
}