记录编号	155727	评测结果	AAAAAAAAAA
题目名称	[NOI 2009]植物大战僵尸	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	0.148 s
提交时间	2015-03-30 07:55:21	内存使用	38.50 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
 
#define Maxm 2000010
#define Maxn 1010
#define F(x,y) ((x-1)*m+y)
#define INF 0x3f3f3f3f
 
using namespace std;
 
struct edge1{
	int x,to,cap;
}E[Maxm];
 
struct edge0{
	int x,to;
}E0[Maxm];
 
vector<int> G[Maxn];
int g[Maxn],tot=1,n,m,tot0=1,cur[Maxn],ind[Maxn],g0[Maxn],c[Maxn],S,T,h[Maxn];
bool v[Maxn];
 
void ade(int x,int y,int v){
	if(x==y) return;
	E[++tot]=(edge1){y,g[x],v}; g[x]=tot;
	E[++tot]=(edge1){x,g[y],0}; g[y]=tot;
}
 
void ade0(int x,int y){
	E0[++tot0]=(edge0){y,g0[x]}; g0[x]=tot0;
	ind[y]++;
}
 
bool Bfs(){
	memset(v,0,sizeof(v));
	queue<int> q;
	q.push(S); v[S]=1; h[S]=0;
	while(!q.empty()){
		int x=q.front(); q.pop();
		for(int i=g[x];i;i=E[i].to){
			int p=E[i].x;
			if(!E[i].cap||v[p]) continue;
			h[p]=h[x]+1;
			q.push(p); v[p]=1;
		}
	}
	return v[T];
}
 
int Dinic(int x,int flow){
	if(x==T||!flow) return flow;
	int f=0;
	for(int &i=cur[x];i;i=E[i].to){
		int p=E[i].x;
		if(h[p]!=h[x]+1||!E[i].cap) continue;
		int tp=Dinic(p,min(flow,E[i].cap));
		E[i].cap-=tp; E[i^1].cap+=tp;
		flow-=tp; f+=tp;
		if(!flow) break;
	}
	if(!f) h[x]=-1;
	return f;
}
 
void getx(int &x,int &y,int i){
	x=((i-1)/m)+1;
	y=i-m*(x-1);
}
 
int main(){
	freopen("pvz.in","r",stdin);
	freopen("pvz.out","w",stdout);
	scanf("%d%d",&n,&m);
	S=F(n,m)+1;
	T=F(n,m)+2;
	for(int i=1,x,y,t;i<=n*m;i++){
		scanf("%d%d",&c[i],&t);
		for(int j=1;j<=t;j++){
			scanf("%d%d",&x,&y);
			x++; y++;
			ade0(i,F(x,y));
		}
		getx(x,y,i);
		if(y<m){
			ade0(F(x,y+1),F(x,y));
		}
	}
	memset(v,0,sizeof(v));
	queue<int> q;
	for(int i=1;i<=n*m;i++)
		if(!ind[i]) q.push(i),v[i]=1;
	while(!q.empty()){
		int x=q.front(); q.pop();
		for(int i=g0[x];i;i=E0[i].to){
			int p=E0[i].x;
			if(v[p]) continue;
			if((--ind[p])==0) q.push(p),v[p]=1;
		}
	}
	int ans=0;
	tot=1;
	for(int i=1;i<=n*m;i++){
		if(!v[i]) continue;
		if(c[i]>0) ade(S,i,c[i]),ans+=c[i];
		else ade(i,T,-c[i]);
		for(int j=g0[i];j;j=E0[j].to){
			int p=E0[j].x;
			if(v[p]) ade(p,i,INF);
		}
	}
	while(Bfs()){
		memcpy(cur,g,sizeof(g));
		ans-=Dinic(S,INF);
	}
	printf("%d\n",ans);
}