TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1953
  • 题目
  • P1953【线性规划与网络流24题 18】分配问题
    限制 : 时间限制 : 1000 MS   空间限制 : 65536 KB
    问题描述

    有n件工作要分配给n个人做。第i个人做第j件工作产生的效益为Cij

    对于给定的n件工作和n个人,计算最优分配方案和最差分配方案。

    输入格式

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

    输出格式

    两行,分别表示最小总效益和最大总效益

    样例输入

    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


    来源  感谢 Wo_ai_WangYuan 放上题目和数据