题目描述
飞行大队有若干个来自各地的驾驶员，专门驾驶一种型号的飞机，这种飞机每架有两个驾驶员，需一个正驾驶员和一个副驾驶员。由于种种原因，例如相互配合的问题，有些驾驶员不能在同一架飞机上飞行，问如何搭配驾驶员才能使出航的飞机最多。
因为驾驶工作分工严格,两个正驾驶员或两个副驾驶员都不能同机飞行。
输入格式
第一行，两个整数 n nn 与 m mm，表示共有 n nn 个飞行员，其中有 m mm 名飞行员是正驾驶员。
下面有若干行，每行有 2 22 个数字 a aa、b bb。表示正驾驶员 a aa 和副驾驶员 b bb 可以同机飞行。
注：正驾驶员的编号在前，即正驾驶员的编号小于副驾驶员的编号。
输出格式
仅一行一个整数，表示最大起飞的飞机数。
样例
样例输入
10 5
1 7
2 6
2 10
3 7
4 8
5 9样例输出
4数据范围与提示
2≤n≤100 2 leq n leq 1002≤n≤100
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn=100+10,maxm=maxn*maxn;
int n,n1;
int fir[maxn],to[maxm],nxt[maxm],cap[maxm],fl[maxm],e=1;
int add(int x,int y) {
to[++e]=y;nxt[e]=fir[x];fir[x]=e;cap[e]=1;fl[e]=0;
to[++e]=x;nxt[e]=fir[y];fir[y]=e;cap[e]=0;fl[e]=0;
}
int maxnow[maxn],last[maxn],zz[maxn];
int EK() {
int s,t,f=0,x,y;
while(1){
memset(maxnow,0,sizeof(maxnow));
s=1;t=1;
maxnow[0]=1;
while(s<=t){
x=zz[s];
for(y=fir[x];y;y=nxt[y]) {
if(!maxnow[to[y]]&&cap[y]>fl[y]) {
maxnow[to[y]]=min(maxnow[x],cap[y]-fl[y]);
last[to[y]]=y;
t++;zz[t]=to[y];
}
}
s++;
if(maxnow[n+1]) break;
}
if(!maxnow[n+1]) break;
x=n+1;
while(x){
y=last[x];
fl[y]+=maxnow[n+1];
fl[y^1]-=maxnow[n+1];
x=to[y^1];
}
f+=maxnow[n+1];
}
return f;
}
int main() {
scanf("%d%d",&n,&n1);
int x,y;
while(scanf("%d%d",&x,&y)==2) add(x,y);
for(int i=1;i<=n1;++i) add(0,i);
for(int i=n1+1;i<=n;++i) add(i,n+1);
cout<<EK();
return 0;
}