stdKonjac's Blog

An AC a day keeps the WA away ~

【分配问题】

题目描述

n 件工作要分配给 n 个人做。第 i 个人做第 j 件工作产生的效益为 cij 。试设计一个将 n 件工作分配给 n 个人做的分配方案,使产生的总效益最大。计算出最优分配方案和最差分配方案。

输入格式

输入文件的第 1 行有 1 个正整数 n (n≤50),表示 n 件工作要分配给 n 个人做。
接下来的 n 行中,每行 n 个整数 cij (cij≤100) ,1≤i≤n,1≤j≤n,表示第 i 个人做第 j 件工作产生的效益为 cij 。

输出格式

输出两行,第一行的一个整数表示最小总效益,第二行的一个整数表示最大总效益。

样例数据 1

输入

5
2 2 2 1 2
2 3 1 2 4
2 0 1 1 1
2 3 4 3 3
3 2 1 2 1

输出

5
14

费用流模板题。把人当做二分图一边,工作当另一边,人与工作之间连一条流量为1费用为工作效率的边,超级点S与每个人连一条流量为1费用为0的边,超级点T与所有工作连一条费用为1流量为0 的边,跑最小费用最大流就是第一问,最大费用最大流就是第二问。

 

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

This site uses Akismet to reduce spam. Learn how your comment data is processed.