同和新媒体矩阵官网同和视频矩阵同和素材矩阵

登录 | 立即注册

同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

2092_AL100飞行员配对方案问题

2022-5-16 18:18| 发布者: Hocassian| 查看: 50| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-3-89504318389200-Problem List-采集的数据-后羿采集器.html

Pro.ID

2092

Title

AL100 飞行员配对方案问题

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=2092

AC

0

Submit

21

Ratio

0.00%

时间&空间限制

Time Limit: 1200/400 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)

描述

第二次世界大战时期，英国皇家空军从沦陷国征募了大量外籍飞行员。由皇家空军派出的每一架飞机都需要配备在航行技能和语言上能互相配合的2 名飞行员，其中1 名是英国飞行员，另1 名是外籍飞行员。在众多的飞行员中，每一名外籍飞行员都可以与其他若干名英国飞行员很好地配合。如何选择配对飞行的飞行员才能使一次派出最多的飞机。对于给定的外籍飞行员与英国飞行员的配合情况，试设计一个算法找出最佳飞行员配对方案，使皇家空军一次能派出最多的飞机。

输入

输入的第一行有2个正整数m和n。n是皇家空军的飞行员总数( n < 100 )；m是外籍飞行员数。外籍飞行员编号为1~m；英国飞行员编号为m+1~n 。
接下来每行有2个正整数 i 和 j ，表示外籍飞行员 i 可以和英国飞行员 j 配合。文件最后以两个 -1 结束。

输出

Description

第二次世界大战时期，英国皇家空军从沦陷国征募了大量外籍飞行员。由皇家空军派出的每一架飞机都需要配备在航行技能和语言上能互相配合的2 名飞行员，其中1 名是英国飞行员，另1 名是外籍飞行员。在众多的飞行员中，每一名外籍飞行员都可以与其他若干名英国飞行员很好地配合。如何选择配对飞行的飞行员才能使一次派出最多的飞机。对于给定的外籍飞行员与英国飞行员的配合情况，试设计一个算法找出最佳飞行员配对方案，使皇家空军一次能派出最多的飞机。

Input

输入的第一行有2个正整数m和n。n是皇家空军的飞行员总数( n < 100 )；m是外籍飞行员数。外籍飞行员编号为1~m；英国飞行员编号为m+1~n 。
接下来每行有2个正整数 i 和 j ，表示外籍飞行员 i 可以和英国飞行员 j 配合。文件最后以两个 -1 结束。

Output

输出最佳飞行员配对方案：第一行是最佳飞行员配对方案一次能派出的最多的飞机数M。接下来M行是最佳飞行员配对方案。每行有2个正整数i和j，表示在最佳飞行员配对方案中，飞行员i和飞行员j配对。
如果所求的最佳飞行员配对方案不存在，则输出 'No Solution!'

Sample Input

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

Sample Output

4
1 7
2 9
3 8
5 10

Author

样例输入

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

样例输出

4
1 7
2 9
3 8
5 10

提示

作者

最新评论

相关分类

返回顶部