【网络流24题】分配问题

2014年3月11日1,9100

题目描述 Description

有n件工作要分配给n个人做。第i 个人做第j 件工作产生的效益为ij c 。试设计一个将
n件工作分配给n个人做的分配方案,使产生的总效益最大。
«编程任务:
对于给定的n件工作和n个人,计算最优分配方案和最差分配方案。

输入描述 Input Description

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

输出描述 Output Description

将计算出的最小总效益和最大总效益输出

样例输入 Sample Input

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

样例输出 Sample Output

5
14

数据范围及提示 Data Size & Hint

把所有人看做二分图中顶点Xi,所有工作看做二分图中顶点Yi,建立附加源S汇T。

1、从S向每个Xi连一条容量为1,费用为0的有向边。
2、从每个Yi向T连一条容量为1,费用为0的有向边。
3、从每个Xi向每个Yj连接一条容量为无穷大,费用为Cij的有向边。

求最小费用最大流,最小费用流值就是最少运费,求最大费用最大流,最大费用流值就是最多运费。