P1517 飄飄乎居士的烏龜
時間: 1000ms / 空間: 131072KiB / Java類名: Main
飄飄乎居士養了烏龜。當然，這些烏龜是用來出售賺取利潤的。
飄飄乎居士的烏龜被安置在了m個窩中。現在，飄飄乎居士已經接到了n個人的定購通知，他們會按順序在來挑選烏龜，其中，第i個人會在pi個窩中挑選烏龜， 但最多隻想買xi隻烏龜。另外，在第i個人購買完烏龜以後，飄飄乎居士會将指定的qi個窩中的龜進行調整，他可以任意調換指定的qi個窩中烏龜數量。飄飄 乎希望知道，在n個人購買完烏龜後，他最多可以出售多少隻烏龜？
輸入格式：第一行，兩個正整數n、m。
接下來一行m個整數（可能為0），第i個整數表示第i個窩中烏龜的數量。
接下來輸入分為n組，每組3行輸入，第i組表示第i個人的資訊：
第一行一個整數xi，表示第i個人最多購買的烏龜數量
第二行一個整數pi以及pi整數，表示該顧客會在pi個指定的窩中挑選烏龜
第三行一個整數qi（qi可能為0）以及跟着的qi個正整數，表示在第i個人購買完烏龜後，飄飄乎居士會調整這qi個窩中烏龜的數量。
輸出格式：一行，表示飄飄乎居士最多出售烏龜的數量。
輸入樣例1： 2 4 2 2 5 0 3 1 3 2 1 4 10 2 4 3 輸入樣例2： 1 2 3 3 4 4 1 2 3 4
輸出樣例1： 7 輸出樣例2：
Hint：樣例一解釋：飄飄乎居士4個窩，初始時，第一個窩裡有2隻烏龜，第二個窩裡有2隻烏龜，第三個窩裡有5隻烏龜；第四窩裡沒有烏龜，共有2位顧客來購買烏龜。
在
第一位顧客到來時，他想在3号窩中挑選烏龜，最多隻想買3隻烏龜。飄飄乎居士将3号窩中的烏龜出售。出售以後，3号窩剩下2隻烏龜，飄飄乎居士可以調整
1、4号窩中烏龜的數量，将1号窩中的2隻烏龜轉入4号窩中，這樣，1号窩沒有烏龜，3号窩2隻烏龜，4号窩有2隻烏龜。
在第二個顧客來時，他想要在3 4号窩中挑選最多10隻烏龜，飄飄乎居士将從1号窩調整到4号窩中的2隻烏龜以及3号窩剩下的2隻烏龜賣出。共賣出7隻烏龜，也就是最後的答案。
資料範圍：0<n、m<=10
每個窩初始時烏龜的數量以及每位顧客購買烏龜的數量<=100000
0<=Pi、qi<=n
資料保證輸入的正确性。
【思路】
最大流。
構圖：
1
對于每個龜窩建立n個結點，建立s t點。
2
連邊：
(s,ui,twi） 表示龜的數量
(ui,tmp,INF)，(tmp,t,xi) tmp為中轉結點，限制pi個點的總流量
(qj,qj+1,INF) 表示烏龜的調換
(ui,ui+1,INF)
【代碼】