[bzoj 2465][中山市选2009] 小球

Description

给定n个不同颜色的球,每个球都有一个分数,同时有m个瓶子,每个瓶子都有固定的容量。现在,你必须把球放到瓶子里面。请编程计算最多能放多少个球到这些瓶子里

Input

输入包含多组数据。

每组数据的第一行为两个整数n, m,分别表示球的个数和瓶子的个数。

接下来的n行,每一行包含一个整数p,表示相应的球的分数。

接下来的m行,每一行包含两个整数c和q, 分别表示每个瓶子的容量(最多能装多少个球)和分数上界(放进该瓶子的每个球的分数都不能超过去q)。

当输入n,m均为0时,表示输入结束。

Output

对于每组数据,输出两个整数B和S,分别表示总共能放进瓶子里的球的最大数目,以及在这个前提下,放进瓶子里面的所有球的最大分数总和。B和S以空格隔开,每组答案独占一行。

Sample Input

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

Sample Output

1 2
2 9

HINT

对于全部的数据,有1<=n<=200,0<=m<=200,1 <= p <= 10^6, 0 <= c <= 200, 1 <= q <= 10^6.

Solution

费用流裸题

首先很容易发现到这是一个二分图,瓶子一边,球一边

建立超级源点S,超级汇点T,有三种连边方式

  1. S->Ball,容量为1,费用为球的分数
  2. Ball->Bottle,容量为1,费用为0
  3. Bottle->T,容量为瓶子可容纳多少球,费用为0

这样我们要求瓶子容纳的球数量最多的情况下费用最大等价于对这张图求最大费用最大流

 

发表评论