传送门 ↬\looparrowright

题目背景

第二次世界大战期间，英国皇家空军从沦陷国征募了大量外籍飞行员。由皇家空军派出的每一架飞机都需要配备在航行技能和语言上能互相配合的两名飞行员，其中一名是英国飞行员，另一名是外籍飞行员。在众多的飞行员中，每一名外籍飞行员都可以与其他若干名英国飞行员很好地配合。

题目描述

一共有 nn 个飞行员，其中有 mm 个外籍飞行员和 (n−m)(n - m) 个英国飞行员，外籍飞行员从 11 到 mm 编号，英国飞行员从 m+1m + 1 到 nn 编号。 对于给定的外籍飞行员与英国飞行员的配合情况，试设计一个算法找出最佳飞行员配对方案，使皇家空军一次能派出最多的飞机。

输入格式

输入的第一行是用空格隔开的两个正整数，分别代表外籍飞行员的个数 mm 和飞行员总数 nn。
从第二行起到倒数第二行，每行有两个整数 u,vu, v，代表外籍飞行员 uu 可以和英国飞行员 vv 配合。
输入的最后一行保证为 -1 -1，代表输入结束。

输出格式

本题存在 Special Judge\text{Special Judge}。
请输出能派出最多的飞机数量，并给出一种可行的方案。
输出的第一行是一个整数，代表一次能派出的最多飞机数量，设这个整数是 kk。
第 22 行到第 k+1k + 1 行，每行输出两个整数 u,vu, v，代表在你给出的方案中，外籍飞行员 uu 和英国飞行员 vv 配合。这 kk 行的 uu 与 vv 应该互不相同。

输入输出样例

输入 #1

5 10
1 7
1 8
2 6
2 9
2 10
3 7
3 8
4 7
4 8
5 10
-1 -1

输出 #1

4
1 7
2 9
3 8
5 10

说明/提示

【数据范围与约定】
对于 $100\%$ 的数据，保证 1⩽m⩽n<1001 \leqslant m \leqslant n < 100，1⩽u⩽m<v⩽n1 \leqslant u \leqslant m < v \leqslant n，同一组配对关系只会给出一次。
【提示】
请注意输入的第一行先读入 mm，再读入 nn。

分析

将外籍飞行员看作点集 S1\mathbb {S_1}，将英国飞行员看作点集 S2\mathbb{S_2}。外籍飞行员 uu 可以和英国飞行员 vv 配合说明存在一条 S1\mathbb{S_1} 中节点 uu 向 S2\mathbb{S_2} 中节点 vv 的边。
转化为二分图最大匹配问题，可用匈牙利算法求解。匈牙利算法中的 match\mathrm{match} 数组自带匹配方案。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 洛谷 P2756
Date: 7/24/2020 
Description: Hungarian Algorithm
*******************************************************************/
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N=104;
struct E
{
	int to;
	int Next;
}edge[N*N];
int n,m;
int tot;
bool vis[N];
int match[N];
int head[N];
inline void add_edge(int,int);
void init();
bool dfs(int);
int main()
{
	init();
	cin>>m>>n;
	int u,v;
	while(~scanf("%d%d",&u,&v))
	{
		if(~u&&~v) add_edge(u,v);
		else break;
	}
	int ans=0,i;
	for(i=1;i<=m;i++)
	{
		memset(vis,0,sizeof(vis));
		if(dfs(i)) ans++;
	}
	cout<<ans<<endl;
	for(i=m+1;i<=n;i++) if(~match[i]) printf("%d %d\n",match[i],i);
	return 0;
}
void init()
{
	memset(head,-1,sizeof(head));
	memset(match,-1,sizeof(match));
}
inline void add_edge(int u,int v)
{
	tot++;
	edge[tot].to=v;
	edge[tot].Next=head[u];
	head[u]=tot;
}
bool dfs(int x)
{
	for(register int i=head[x];~i;i=edge[i].Next)
	{
		int y=edge[i].to;
		if(!vis[y])
		{
			vis[y]=1;
			if(match[y]==-1||dfs(match[y]))
			{
				match[y]=x;
				return 1;
			}
		}
	}
	return 0;
}