P2756 飞行员配对方案问题 二分图匹配 匈牙利算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了P2756 飞行员配对方案问题 二分图匹配 匈牙利算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2642字，纯文字阅读大概需要4分钟。
内容图文
题目背景
第二次世界大战时期..
题目描述
英国皇家空军从沦陷国征募了大量外籍飞行员。由皇家空军派出的每一架飞机都需要配备在航行技能和语言上能互相配合的2 名飞行员，其中1 名是英国飞行员，另1名是外籍飞行员。在众多的飞行员中，每一名外籍飞行员都可以与其他若干名英国飞行员很好地配合。如何选择配对飞行的飞行员才能使一次派出最多的飞机。对于给定的外籍飞行员与英国飞行员的配合情况，试设计一个算法找出最佳飞行员配对方案，使皇家空军一次能派出最多的飞机。
对于给定的外籍飞行员与英国飞行员的配合情况，编程找出一个最佳飞行员配对方案，使皇家空军一次能派出最多的飞机。
输入格式
第 1 行有 2 个正整数 m 和 n。n 是皇家空军的飞行员总数(n<100)；m 是外籍飞行员数(m<=n)。外籍飞行员编号为 1~m；英国飞行员编号为 m+1~n。
接下来每行有 2 个正整数 i 和 j，表示外籍飞行员 i 可以和英国飞行员 j 配合。最后以 2个-1 结束。
输出格式
第 1 行是最佳飞行员配对方案一次能派出的最多的飞机数 M。接下来 M 行是最佳飞行员配对方案。每行有 2个正整数 i 和 j，表示在最佳飞行员配对方案中，飞行员 i 和飞行员 j 配对。如果所求的最佳飞行员配对方案不存在，则输出‘No Solution!’。
输入输出样例
输入 #15 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? ???查看题解
这一道题 就是一个非常简单的二分图匹配问题
这里还是稍微复习一下练练手吧
首先第一问自然是非常的简单 就是直接输出一个二分图匹配的最大匹配就可以了
问题是怎么输出配对？
这是一个神奇的问题
其实也就是非常的简单（由他人博客知
那个二分图不是从hav数组是从右边连向左边吗
也就是说从英国连向外籍 那么我们只需要枚举一下外籍飞行员 如果它的hav不为0 就输出hav[i]和i 也就是所对应的的左边的英国飞行员和外籍飞行员
具体看代码咯
#include<bits/stdc++.h>
#define maxn 105
using namespace std;
vector<int> v[maxn];
int vis[maxn],hav[maxn];int tim;
bool Dfs(int rt)
{
for(int i=0;i<v[rt].size();i++)
{
int to=v[rt][i];
if(vis[to]!=tim)
{
vis[to]=tim;
if(!hav[to]||Dfs(hav[to]))
{
hav[to]=rt;
return true;
}
}
}
return false;
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
int x,y;
while(~scanf("%d%d",&x,&y))
{
if(x==-1&&y==-1) break;
v[x].push_back(y);
}
int ans=0;
for(int i=1;i<=n;i++)
{
tim++;ans+=Dfs(i);
}
printf("%d\n",ans);
for(int i=1;i<=m;i++)
if(hav[i])
printf("%d %d\n",hav[i],i);
return 0;
}
习题练习
A 部分习题 —（Hungarian算法）：
<1> 飞行员配对方案问题 https://www.luogu.org/problemnew/show/2756
<2> [SCOI2010]连续攻击游戏 https://www.luogu.org/problemnew/show/P1640
<3> [ZJOI2009]假期的宿舍 https://www.luogu.org/problemnew/show/P2055
<4> [ZJOI2007]矩阵游戏 https://www.luogu.org/problemnew/show/P1129
<5> 酒店之王 https://www.luogu.org/problemnew/show/P1402
B 部分习题 —（二分图相关定理）：
<1> [USACO11NOV]牛的障碍 https://www.luogu.org/problemnew/show/P3033
C 部分习题 —（KM算法）：
<1> 运动员最佳匹配问题 https://www.luogu.org/problemnew/show/1559
内容总结
以上是互联网集市为您收集整理的P2756 飞行员配对方案问题 二分图匹配 匈牙利算法全部内容，希望文章能够帮你解决P2756 飞行员配对方案问题 二分图匹配 匈牙利算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。