记录编号	155699	评测结果	AAAAAAAAAA
题目名称	[NOI 2009]植物大战僵尸	最终得分	100
用户昵称	HouJikan	是否通过	通过
代码语言	C++	运行时间	0.116 s
提交时间	2015-03-29 22:10:36	内存使用	0.35 MiB

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <vector>
#include <ctime>
#include <functional>
#define pritnf printf
#define scafn scanf
#define sacnf scanf
#define For(i,j,k) for(int i=(j);i<=(k);(i)++)
#define Clear(a) memset(a,0,sizeof(a))
using namespace std;
typedef unsigned int Uint;
const int INF=0x7fffffff;
const double eps=1e-10;
///==============struct declaration==============
struct adj{
	int from,to,cap,flow;
	adj(int from=0,int to=0,int cap=0,int flow=0):from(from),to(to),cap(cap),flow(flow){}
};
///==============var declaration=================
const int MAXN=610;
int n,m,tot,S,E,SM=0;
int Score[25][35],Ind[MAXN];
int cur[MAXN],gap[MAXN],pa[MAXN],d[MAXN];
vector <int> G[MAXN],rEdge[MAXN];
vector <adj> Edge;
///==============function declaration============
int ID(int r,int c){return r*m+c+1;}
void add_edge(int from,int to,int cap,int flow);void BFS();
int argument();void MaxFlow();
void KillCircle();
///==============main code=======================
int main()
{
	//#define FILE__
	//#ifdef FILE__
	freopen("pvz.in","r",stdin);
	freopen("pvz.out","w",stdout);
	//#endif // FILE__
   scanf("%d%d",&n,&m);
	S=0,E=n*m+1;
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++){
			int w;
			scanf("%d%d",&Score[i][j],&w);
			while(w--){
				int r,c;scanf("%d%d",&r,&c);
				add_edge(ID(r,c),ID(i,j),INF,0);
				rEdge[ID(i,j)].push_back(ID(r,c));
				Ind[ID(r,c)]++;
			}
			if (Score[i][j]>=0){add_edge(S,ID(i,j),Score[i][j],0);}
			else add_edge(ID(i,j),E,-Score[i][j],0);
			if (j!=0){
				add_edge(ID(i,j-1),ID(i,j),INF,0);
				rEdge[ID(i,j)].push_back(ID(i,j-1));
				Ind[ID(i,j-1)]++;
			}
		}
	KillCircle();
	MaxFlow();
   return 0;
}
///================fuction code====================
void add_edge(int from,int to,int cap,int flow){
	G[from].push_back(tot++);G[to].push_back(tot++);
	Edge.push_back(adj(from,to,cap,flow));Edge.push_back(adj(to,from,0,0));
}
void BFS(){
	queue <int> Q;Q.push(E);
	memset(gap,0,sizeof(gap));memset(d,-1,sizeof(d));d[E]=0;
	while (!Q.empty()){
		int x=Q.front();Q.pop();
		gap[d[x]]++;
		int siz=G[x].size();
		for(int i=0;i<siz;i++){
			adj &e=Edge[G[x][i]];
			if (d[e.to]==-1){
				d[e.to]=d[x]+1;
				Q.push(e.to);
			}
		}
	}
}
int argument(){
	int flow=INF,x=E;
	while (x!=S){
		flow=min(flow,Edge[pa[x]].cap-Edge[pa[x]].flow);
		x=Edge[pa[x]].from;
	}
	x=E;
	while (x!=S){
		Edge[pa[x]].flow+=flow;
		Edge[pa[x]^1].flow-=flow;
		x=Edge[pa[x]].from;
	}
	return flow;
}
void MaxFlow(){
	int flow=0;
	memset(cur,0,sizeof(cur));
	BFS();
	int x=S;
	while (d[x]<=E){
		if (x==E){
			flow+=argument();
			x=S;
		}
		int siz=G[x].size();
		bool suc=false;
		for(int i=cur[x];i<siz;i++){
			adj &e=Edge[G[x][i]];
			if (d[e.to]==d[x]-1&&e.cap>e.flow&&Ind[e.to]==0){
				cur[x]=i;pa[e.to]=G[x][i];
				suc=true;x=e.to;break;
			}
		}
		if (!suc){
			int mind=E;
			for(int i=0;i<siz;i++){
				adj &e=Edge[G[x][i]];
				if (e.cap>e.flow&&Ind[e.to]==0)
					mind=min(mind,d[e.to]);
			}
			if (--gap[d[x]]==0) break;
			gap[d[x]=mind+1]++;
			cur[x]=0;
			if (x!=S)
				x=Edge[pa[x]].from;
		}
	}
	printf("%d\n",SM-flow);
}
void KillCircle(){
	queue <int> Q;
	for(int i=1;i<=n*m;i++)
		if (Ind[i]==0) Q.push(i);
	while (!Q.empty()){
		int x=Q.front();Q.pop();
		int r=(x-1)/m;int c=(x-1)%m;
		if (Score[r][c]>=0)SM+=Score[r][c];
		int siz=rEdge[x].size();
		for(int i=0;i<siz;i++){
			int &e=rEdge[x][i];
			if (--Ind[e]==0)
				Q.push(e);
		}
	}
}