夜间模式
字体
阴影
滤镜
主题色
网络流 24 题 – 分配问题

题面

题目传送

题目描述

有 $ n $ 件工作要分配给 $ n $ 个人做。第 $ i $ 个人做第 $ j $ 件工作产生的效益为 $ c_{ij} $。试设计一个将 $ n $ 件工作分配给 $ n $ 个人做的分配方案,使产生的总效益最大。

输入格式

第 $ 1 $ 行有 $ 1 $ 个正整数 $ n $,表示有 $ n $ 件工作要分配给 $ n $ 个人做。接下来的 $ n $ 行中,每行有 $ n $ 个整数 $ c_{ij} $,表示第 $ i $ 个人做第 $ j $ 件工作产生的效益为 $ c_{ij} $。

输出格式

两行分别输出最小总效益和最大总效益。

思路

裸的二分图最佳完美匹配,这里用费用流解决。

需要注意的是求最大值的情况可以用小技巧,将边权取相反数,求出的费用再次取相反数即可。

代码

暂无评论

发送评论


				
上一篇
下一篇