记录编号	587123	评测结果	AAAAAAAAAA
题目名称	[网络流24题] 搭配飞行员	最终得分	100
用户昵称	Untitled	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2024-03-14 20:45:30	内存使用	0.00 MiB

#include <bits/stdc++.h>
using namespace std;

int const N=210;
int n,nl,res;
int f[N*2][N*2],d[N*2],level[N*2];
struct node{
	int id,lv;
};

bool bfs(){
	queue<node> q;
	memset(level,0,sizeof(level));
	memset(d,0,sizeof(d));
	node t;int x,lv;
	q.push(node{0,1});
	while (q.size()){
		t=q.front();q.pop();
		x=t.id,lv=t.lv,d[x]=1;
		level[x]=(!level[x]?lv:min(lv,level[x]));
		for (int i=0;i<=n+1;i++){
			if (i==x || d[i] || !f[x][i]) continue;
			q.push(node{i,lv+1});
		}
	} 
	return level[n+1];
}

int dfs(int x,int minn){
	if (x==n+1) return minn;
	int k,cnt=0;
	for (int i=0;i<=n+1;i++){
		if (i==x || level[x]+1!=level[i] || !f[x][i]) continue;
		k=dfs(i,min(minn,f[x][i]));
		minn-=k,cnt+=k,f[x][i]-=k,f[i][x]+=k;
		if (!minn) break;
	}
	return cnt;
}

int main(){
	freopen("flyer.in","r",stdin);
	freopen("flyer.out","w",stdout);
	
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	
	int a,b;
	cin>>n>>nl;
	while (cin>>a>>b){
		f[a][b]=1;
		
	}
	for (int i=1;i<=nl;i++) f[0][i]=1;
	for (int i=nl+1;i<=n;i++) f[i][n+1]=1;
	
	while (bfs()){
		res+=dfs(0,INT_MAX);
	}
	cout<<res;
	
	return 0;
}