Bzoj1565 [NOI2009]植物大戰僵屍

圖論 網絡流最小割+拓撲排序

Time Limit: 10 Sec  Memory Limit: 64 MB

Submit: 2363  Solved: 1092

僅包含一個整數，表示可以獲得的最大能源收入。注意，你也可以選擇不進行任何攻擊，這樣能源收入為0。

3 2

10 0

20 0

-10 0

-5 1 0 0

100 1 2 1

100 0

25

在樣例中, 植物P1,1可以攻擊位置(0,0), P2, 0可以攻擊位置(2,1)。 

一個方案為，首先進攻P1,1, P0,1，此時可以攻擊P0,0 。共得到能源收益為(-5)+20+10 = 25。注意, 位置(2,1)被植物P2,0保護，是以無法攻擊第2行中的任何植物。 

【大緻資料規模】

約20%的資料滿足1 ≤ N, M ≤ 5；

約40%的資料滿足1 ≤ N, M ≤ 10；

約100%的資料滿足1 ≤ N ≤ 20，1 ≤ M ≤ 30，-10000 ≤ Score ≤ 10000 。

網絡流+拓撲排序

因為植物可能會互相保護而形成環，是以先用拓撲排序排除環，求出圖中的閉合子圖。

然後按照先吃右邊才能吃左邊的關系，從每個點向它左邊一格的點連邊，容量為INF

保護型的植物向它保護的植物連邊，容量為INF。

吃植物能獲得收益時，該植物向彙點連邊，容量為收益。

吃植物需要代價時，源點向該植物連邊，容量為代價的絕對值。

答案=可能獲得的收益總和-最小割。

本文為部落客原創文章，轉載請注明出處。