題目描述

Plants vs. Zombies（PVZ）是最近十分風(fēng)靡的一款小游戲。Plants（植物）和Zombies（僵尸）是游戲的主角，其中Plants防守，而Zombies進(jìn)攻。該款游戲包含多種不同的挑戰(zhàn)系列，比如PRotect Your Brain、Bowling等等。其中最為經(jīng)典的，莫過于玩家通過控制Plants來防守Zombies的進(jìn)攻，或者相反地由玩家通過控制Zombies對Plants發(fā)起進(jìn)攻。

現(xiàn)在，我們將要考慮的問題是游戲中Zombies對Plants的進(jìn)攻，請注意，本題中規(guī)則與實(shí)際游戲有所不同。游戲中有兩種角色，Plants和Zombies，每個(gè)Plant有一個(gè)攻擊位置集合，它可以對這些位置進(jìn)行保護(hù)；而Zombie進(jìn)攻植物的方式是走到植物所在的位置上并將其吃掉。

游戲的地圖可以抽象為一個(gè)N行M列的矩陣，行從上到下用0到N–1編號(hào)，列從左到右用0到M–1編號(hào)；在地圖的每個(gè)位置上都放有一個(gè)Plant，為簡單起見，我們把位于第r行第c列的植物記為Pr, c。

Plants分很多種，有攻擊類、防守類和經(jīng)濟(jì)類等等。為了簡單的描述每個(gè)Plant，定義Score和Attack如下：

Score[Pr, c]

Zombie擊潰植物Pr, c可獲得的能源。若Score[Pr, c]為非負(fù)整數(shù)，則表示擊潰植物Pr, c可獲得能源Score[Pr, c]，若為負(fù)數(shù)表示擊潰Pr, c需要付出能源 -Score[Pr, c]。

Attack[Pr, c]

植物Pr, c能夠?qū)ombie進(jìn)行攻擊的位置集合。

Zombies必須從地圖的右側(cè)進(jìn)入，且只能沿著水平方向進(jìn)行移動(dòng)。Zombies攻擊植物的唯一方式就是走到該植物所在的位置并將植物吃掉。因此Zombies的進(jìn)攻總是從地圖的右側(cè)開始。也就是說，對于第r行的進(jìn)攻，Zombies必須首先攻擊Pr, M-1；若需要對Pr, c（0≤c<M-1）攻擊，必須將Pr,M-1, Pr, M-2 … Pr, c+1先擊潰，并移動(dòng)到位置(r, c)才可進(jìn)行攻擊。

在本題的設(shè)定中，Plants的攻擊力是無窮大的，一旦Zombie進(jìn)入某個(gè)Plant的攻擊位置，該Zombie會(huì)被瞬間消滅，而該Zombie沒有時(shí)間進(jìn)行任何攻擊操作。因此，即便Zombie進(jìn)入了一個(gè)Plant所在的位置，但該位置屬于其他植物的攻擊位置集合，則Zombie會(huì)被瞬間消滅而所在位置的植物則安然無恙（在我們的設(shè)定中，Plant的攻擊位置不包含自身所在位置，否則你就不可能擊潰它了）。

Zombies的目標(biāo)是對Plants的陣地發(fā)起進(jìn)攻并獲得最大的能源收入。每一次，你可以選擇一個(gè)可進(jìn)攻的植物進(jìn)行攻擊。本題的目標(biāo)為，制定一套Zombies的進(jìn)攻方案，選擇進(jìn)攻哪些植物以及進(jìn)攻的順序，從而獲得最大的能源收入。

輸入輸出格式

輸入文件pvz.in的第一行包含兩個(gè)整數(shù)N, M，分別表示地圖的行數(shù)和列數(shù)。

接下來N×M行描述每個(gè)位置上植物的信息。第r×M + c + 1行按照如下格式給出植物Pr, c的信息：第一個(gè)整數(shù)為Score[Pr, c], 第二個(gè)整數(shù)為集合Attack[Pr, c]中的位置個(gè)數(shù)w，接下來w個(gè)位置信息（r’, c’），表示Pr, c可以攻擊位置第r’ 行第c’ 列。

輸出文件pvz.out僅包含一個(gè)整數(shù)，表示可以獲得的最大能源收入。注意，你也可以選擇不進(jìn)行任何攻擊，這樣能源收入為0。

輸入輸出樣例

3 210 020 0-10 0-5 1 0 0100 1 2 1100 0輸出樣例#1：
25
說明
約20%的數(shù)據(jù)滿足1 ≤ N, M ≤ 5；
約40%的數(shù)據(jù)滿足1 ≤ N, M ≤ 10；
約100%的數(shù)據(jù)滿足1 ≤ N ≤ 20，1 ≤ M ≤ 30，-10000 ≤ Score ≤ 10000
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
最小割+拓?fù)渑判騸
利用拓?fù)渑判虬循h(huán)去掉，剩下的就是能攻擊的部分，然后建圖跑一遍最小割就可以了~
（看起來很夸張，可是很好寫啊~）
#include<cstdio>#include<cstring>#include<iostream>#include<queue>using namespace std;#define dd(i,j) (i-1)*m+j#define inf 999999999int n,m,T,x,y,z,du[601],val[601],fi[10001],w[1000001],ne[1000001],fi2[10001],w2[1000001],ne2[1000001],tot,v[1000001],cnt,ans,dis[1000001];bool b[601];void add(int u,int v){	du[v]++;	w[++cnt]=v;ne[cnt]=fi[u];fi[u]=cnt;}void add2(int u,int vv,int val){	w2[++cnt]=vv;ne2[cnt]=fi2[u];fi2[u]=cnt;v[cnt]=val;	w2[++cnt]=u;ne2[cnt]=fi2[vv];fi2[vv]=cnt;}void dfs(int u){	b[u]=1;	for(int i=fi[u];i;i=ne[i]) if(!b[w[i]]) dfs(w[i]);}void topsort(){	queue<int> q;	for(int i=1;i<=n*m;i++)	  if(!du[i]) q.push(i);	  else b[i]=1;	while(!q.empty())	{		int k=q.front();q.pop();b[k]=0;		for(int i=fi[k];i;i=ne[i])		{			du[w[i]]--;			if(!du[w[i]]) q.push(w[i]);		}	}	for(int i=1;i<=n*m;i++) if(b[i]) dfs(i);}void rebuild(){	cnt=1;T=n*m+1;	for(int i=1;i<=n*m;i++)	  if(!b[i])	  {	  	if(val[i]>0) tot+=val[i],add2(i,T,val[i]);	  	else add2(0,i,-val[i]);	  	for(int j=fi[i];j;j=ne[j])	  	  if(!b[w[j]]) add2(i,w[j],inf);	  }}bool bfs(){	queue<int> q;	memset(dis,-1,sizeof(dis));	q.push(0);dis[0]=0;	while(!q.empty())	{		int k=q.front();q.pop();		for(int i=fi2[k];i;i=ne2[i])		  if(v[i]>0 && dis[w2[i]]==-1)		  {		  	dis[w2[i]]=dis[k]+1;q.push(w2[i]);		  }	}	if(dis[T]==-1) return 0;	return 1;}int findd(int u,int vv){	if(u==T) return vv;	int kkz,totnum=0;	for(int i=fi2[u];i;i=ne2[i])	  if(v[i]>0 && dis[w2[i]]==dis[u]+1 && (kkz=findd(w2[i],min(vv-totnum,v[i]))))	  {	  	v[i]-=kkz;v[i^1]+=kkz;totnum+=kkz;	  	if(totnum==vv) return totnum;	  }	if(!totnum) dis[u]=-1;	return totnum;}int main(){	scanf("%d%d",&n,&m);	for(int i=1;i<=n;i++)	  for(int j=1;j<=m;j++)	  {	  	scanf("%d",&val[dd(i,j)]);	  	scanf("%d",&x);	  	while(x--)	  	{	  		scanf("%d%d",&y,&z);y++;z++;add(dd(i,j),dd(y,z));		}	  }	for(int i=1;i<=n;i++)	  for(int j=2;j<=m;j++) add(dd(i,j),dd(i,j-1));	topsort();rebuild();	while(bfs()) ans+=findd(0,inf);	printf("%d/n",tot-ans);	return 0;}