TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1513
  • 题目
  • P1513稳定的奶牛分配
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    农夫约翰有N(1<=N<=1000)只奶牛,每只奶牛住在B(1<=B<=20)个奶牛棚中的一个。当然,奶牛棚的容量有限。有些奶牛对它现在住的奶牛棚很满意,有些就不太满意了。

    农夫约翰想要重新安排这些奶牛,使得奶牛的满意度尽可能相同,尽管有可能这意味者所有的奶牛都不喜欢新分配的奶牛棚。

    每只奶牛都按顺序给出她喜欢的奶牛棚。在某个分配方案中,一只奶牛的满意度等于她对她的奶牛棚的评价等级。你的工作是找出一种分配方案使得没有奶牛棚超出它的容量,而且奶牛给分配到的奶牛棚的评价等级的相对范围(即分配到的等级最高的奶牛棚和等级最低的奶牛棚之间的差值)尽可能的小。


    输入格式

    第1行:两个用空格隔开的整数,N和B
    第2..N+1行:每一行都有B个用空格隔开的正整数,它们恰好是1到B的一个排列。第i+1行的第一个整数是第i只奶牛的首选牛棚的编号,该行的第二个整数是第i只奶牛的第二选择,等等。
    第N+2行:B个用空格隔开的整数,分别表示这B个奶牛棚的容量。这些数的和保证至少为N。

    输出格式

    一个整数,被分配到的牛棚等级的最小相对差值,输出得到该相对差时所包含的不同等级的牛棚个数。

    样例输入

    6 4
    1 2 3 4
    2 3 1 4
    4 2 3 1
    3 1 2 4
    1 3 4 2
    1 4 2 3
    2 1 3 2

    样例输出

    2

    提示

    每个奶牛都被安排在它的第一选择或第二选择:1号牛棚安排1号奶牛和5号奶牛,2号牛棚安排2号奶牛,3号牛棚安排4号奶牛,4号牛棚安排3号奶牛和6号奶牛。

    输出样例
    表示得到最小相对差为1,这时奶牛们入住进了两种不同等级的牛棚


    来源  网络流 usaco feb06 gold