记录编号	249086	评测结果	AAAAAAAAAA
题目名称	[NOI 2009]植物大战僵尸	最终得分	100
用户昵称	TenderRun	是否通过	通过
代码语言	C++	运行时间	0.905 s
提交时间	2016-04-11 22:37:10	内存使用	25.90 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
const int maxr=50,maxc=50;
const int maxn=1050;
const int maxm=200010;
const int INF=23333333;
int R,C,id[maxr][maxc],def[maxr*maxc],G[maxr*maxc][maxr*maxc],sum;
int cnt=1,fir[maxn],nxt[maxm<<1],to[maxm<<1],cap[maxm<<1],v[maxr][maxc];
void addedge(int a,int b,int c){
	nxt[++cnt]=fir[a];fir[a]=cnt;to[cnt]=b;cap[cnt]=c;
}
int dis[maxn],gap[maxn],path[maxn],fron[maxn];
queue<int>q;
void BFS(){
	memset(dis,0,sizeof(dis));
	dis[R*C+1]=1;q.push(R*C+1);
	while(!q.empty()){
		int x=q.front();q.pop();
		for(int i=fir[x];i;i=nxt[i])
			if(!dis[to[i]]&&!def[to[i]])
				dis[to[i]]=dis[x]+1,
					q.push(to[i]);
	}
}
int ISAP(){
	BFS();
	for(int i=0;i<=R*C+1;i++){
		gap[dis[i]]++;
		fron[i]=fir[i];
	}
	int p=0,f,ret=0;
	while(dis[0]<=R*C+2){
		if(p==R*C+1){
			f=INF;
			while(p){
				f=min(f,cap[path[p]]);
				p=to[path[p]^1];
			}
			p=R*C+1;ret+=f;
			while(p){
				cap[path[p]]-=f;
				cap[path[p]^1]+=f;
				p=to[path[p]^1];
			}
		}
		int &ii=fron[p];
		for(;ii;ii=nxt[ii])
			if(cap[ii]&&dis[to[ii]]==dis[p]-1&&!def[to[ii]])
				break;
		if(ii)
			path[p=to[ii]]=ii;
		else{
			if(--gap[dis[p]]==0)break;
			int Min=R*C+3;
			for(int i=fir[p];i;i=nxt[i])
				if(cap[i]&&!def[to[i]])
					Min=min(Min,dis[to[i]]);
			++gap[dis[p]=Min+1];
			fron[p]=fir[p];
			if(p)p=to[path[p]^1];		
		}		
	}
	return ret;
}
void DFS(int x){
	for(int i=1;i<=R*C;i++)
		if(!def[i]&&G[x][i]){
			def[i]=true;
			DFS(i);
		}
}
int main(){
	freopen("pvz.in","r",stdin);
	freopen("pvz.out","w",stdout);
	scanf("%d%d",&R,&C);
	for(int i=1;i<=R;i++)
		for(int j=1;j<=C;j++)
			id[i][j]=(i-1)*C+j;
	for(int i=1;i<=R;i++)
		for(int j=1,x,a,b;j<=C;j++){
			scanf("%d%d",&v[i][j],&x);
			while(x--){
				scanf("%d%d",&a,&b);a++;b++;
				G[id[i][j]][id[a][b]]=true;
				addedge(id[a][b],id[i][j],INF);
				addedge(id[i][j],id[a][b],0);
			}
			if(j>1){
				G[id[i][j]][id[i][j-1]]=true;
				addedge(id[i][j-1],id[i][j],INF);
				addedge(id[i][j],id[i][j-1],0);
			}
		}
			

	for(int k=1;k<=R*C;k++)
		for(int i=1;i<=R*C;i++)
			for(int j=1;j<=R*C;j++)
				G[i][j]|=G[i][k]&&G[k][j];
	
	for(int i=1;i<=R*C;i++)
		if(G[i][i])
			def[i]=true;
	
	for(int i=1;i<=R*C;i++)
		if(def[i])
			DFS(i);		
		
	for(int i=1;i<=R;i++)
		for(int j=1;j<=C;j++)
			if(!def[id[i][j]]){
				if(v[i][j]>0){
					sum+=v[i][j];
					addedge(0,id[i][j],v[i][j]);
					addedge(id[i][j],0,0);
				}
				else
					addedge(id[i][j],R*C+1,-v[i][j]),
					addedge(R*C+1,id[i][j],0);	
			}
			
	printf("%d\n",sum-ISAP());		
	return 0;
}