网络流24题之飞行员配对方案问题

题目链接：传送门

二分图匹配（匈牙利）当然可以网络流写，但是二分图匹配明显简单一些，裸的，这里就不详细讲了。接下来上代码

#include<bits/stdc++.h>
#define rg register
using namespace std;
typedef long long ll;
inline int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9')  f= (c=='-')?-1:1,c=getchar();
    while(c>='0'&&c<='9')  x=x*10+c-48,c=getchar();
    return f*x;
}
struct node{
    int to,next;	
}a[10001];
int head[10001],f[10001],b[10001],cnt;
void add(int x,int y){
    a[++cnt].to=y;
    a[cnt].next=head[x];
    head[x]=cnt;
}
int find(int k){
    for(int i=head[k];i;i=a[i].next){
        int v=a[i].to;
        if(!f[v]){
            f[v]=1;
            if(find(b[v])||!b[v]){
                b[k]=v;
                b[v]=k;
                return 1;
            }
        }
    }
    return 0;
}
int main(){
    int n,m,x,y,ans=0;
    n=read(),m=read();
    while(scanf("%d%d",&x,&y)!=EOF){
        if(x==-1&&y==-1)
            break;
        y+=n;
        add(x,y);
        add(y,x);
    }
    for(int i=1;i<=n;i++){
        memset(f,0,sizeof(f));
        ans+=find(i);
    }
    if(ans==0)
        printf("No Solution!"),exit(0);
    printf("%d
",ans);
    for(int i=1;i<=n;i++)
        if(b[i])
            printf("%d %d
",i,b[i]-n);
}