洛谷 P2756 飞行员配对方案问题 & LOJ #6000「网络流 24 题」搭配飞行员

题面

洛谷 P2756 飞行员配对方案问题

LOJ #6000.「网络流 24 题」搭配飞行员

因为 LOJ 上的版本比较简洁,所以就放这个版本的题面了。

飞行大队有若干个来自各地的驾驶员,专门驾驶一种型号的飞机,这种飞机每架有两个驾驶员,需一个正驾驶员(英国)和一个副驾驶员(外籍)。由于种种原因,例如相互配合的问题,有些驾驶员不能在同一架飞机上飞行,问如何搭配驾驶员才能使出航的飞机最多。

因为驾驶工作分工严格,两个正驾驶员或两个副驾驶员都不能同机飞行。

思路

二分图匹配问题。可以使用匈牙利算法解决,因为弱不会,所以用网络流求解。

如果一个英国驾驶员可以配对一个外籍驾驶员,那么就将他们两个连一条边(权值为 $1$ )。

然后定义 S 点和 T 点分别为源点和汇点。因为数据很小,所以这里我将 S 点和 T 点编号分别定为 2333 和 2334 。

将 S 与所有英国驾驶员连一条边,T 与所有外籍驾驶员连一条边。

然后求从 S 到 T 的最大流即可。

注意

洛谷版本的题面需要输出配对方案,我们用 $res[i]$ 来表示 $i$ 点的上一个点,在 EK 时更新这个数组即可。

代码

洛谷版本

LOJ 版本

LOJ 上这道题更简单,不需要记录方案。但和洛谷上有一些细节的不同,需要注意。

 

暂无评论

发送评论


				
上一篇
下一篇