TouchStone
  Please Login
Login Sign Up
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P1513
  • Problem
  • P1513稳定的奶牛分配
    Limits : Time Limit : 10000 MS   Memory Limit : 65536 KB
    Description

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

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

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


    Input Format

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

    Output Format

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

    Sample Input 1

    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

    Sample Output 1

    2

    Sample Input 2

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

    Sample Output 2

    1

    Hint

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

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


    Source  网络流 usaco feb06 gold