Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom2年前

08/20
18:19
最大流

[bzoj 1280 poj 1149] Emmy卖猪pigs

00:00/00:00

20150113100124_2ns3S.thumb.700_0   20141221204942_42vSL.thumb.700_0

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

Emmy在一个养猪场工作。这个养猪场有M个锁着的猪圈,但Emmy并没有钥匙。顾客会到养猪场来买猪,一个接着一个。每一位顾客都会有一些猪圈的钥匙,他们会将这些猪圈打开并买走固定数目的猪。 所有顾客有的钥匙和他们需要买猪的数量在事先都告诉了Emmy,于是Emmy要订一个计划,使得卖出去的猪最多。 买卖的过程是这样的:一个顾客前来,并打开所有他可以打开的猪圈。

然后Emmy从这些猪圈里牵出固定数目的猪卖给顾客(最多只能和顾客需要数相等),并可以重新安排这些开着的猪圈中的猪。 每个猪圈可以存放任意数目的猪。 写一个程序,使得Emmy能够卖出去尽可能多的猪。

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

第一行有两个整数:M和N,表示猪圈数和顾客数。 第二行有M个整数,表示每个猪圈初始时有多少猪。 接下来的N行按照前来的次序描述了每一个顾客,每行的格式如下: A K1 K2…KA B A表示该顾客拥有的钥匙数,K1...KA表示每个钥匙所对应的猪圈,B表示该顾客需要购买的猪的数目。

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

仅包含一个整数,即最多能卖出去的猪的数目。

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

3 3
3 1 10
2 1 2 2
2 1 3 3
1 2 6

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

7

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

1 ≤ M ≤ 1000,1 ≤ N ≤ 100

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

本题的关键在于如何构造一个容量网络。在本题中,容量网络的构造方法如下。
   (1)将顾客看作除源点和汇点以外的结点,并且另外设两个结点:源点和汇点。
   (2)源点和每个猪圈的第一个顾客连边,边的权是开始时猪圈中猪的数目。
   (3)若源点和某个结点之间有重边,则将权合并(因此源点流出的流量就是所有猪圈能提供的猪的数目)
   (4)顾客j紧跟顾客i之后打开某个猪圈,则边<i,j>的权是+∞;这是因为,如果顾客j紧跟顾客i之后打开某个猪圈,那么Mike就有可能根据顾客j的需求将其他猪圈中的猪调整到该猪圈,这样顾客j就能买到尽可能多的猪。
   (5)每个顾客和汇点之间连边,边的权是顾客所希望购买的猪的数目(因此汇点的流入量就是每个顾客所购买的猪的个数)
c++:
pascal:

trim

[bzoj 1280 poj 1149] Emmy卖猪pigs