记录编号	412592	评测结果	AAAAAAAAAA
题目名称	[NOI 2009]植物大战僵尸	最终得分	100
用户昵称	Imone NOI2018Au	是否通过	通过
代码语言	C++	运行时间	0.112 s
提交时间	2017-06-09 19:11:01	内存使用	14.14 MiB

#include <cstring>
#include <cstdio>
#include <algorithm>
#define MAXN 610
#define MAXM 724818
#define S 608
#define T 609
#define plid(r, c) ((r) * M + (c))
#define INF 0x3f3f3f3f
using namespace std;

int N, M;

///////////DINIC////////////////
namespace dinic {
	int head[MAXN], cur[MAXN], next[MAXM], tail[MAXM], flow[MAXM], id = 0;
	inline void _link(int u, int v, int f) {
		next[id] = head[u]; tail[id] = v; flow[id] = f; head[u] = id++;
	}
	inline void link(int u, int v, int f) {
		_link(u, v, f); _link(v, u, 0);
	}
	
	int Q[MAXN], qH, qT, dis[MAXN];
	bool bfs() {
		int u, v, i;
		memset(dis, 0x3f, sizeof(dis));
	
		qH = qT = 0;
		Q[qT++] = S; dis[S] = 0;
	
		while(qH < qT) {
			u = Q[qH++];
			for(i=head[u];i!=-1;i=next[i]) {
				v = tail[i];
				if(flow[i] > 0 && dis[v] == INF) {
					dis[v] = dis[u] + 1;
					Q[qT++] = v;
				}
			}
		}
		return dis[T] != INF;
	}
	
	int dfs(int u, int r) {
		if(u == T || !r) return r;
	
		int v, ans = 0, t;
		for(int &i=cur[u];i!=-1;i=next[i]) {
			v=tail[i];
			if(dis[v] == dis[u] + 1 && flow[i] > 0 && (t = dfs(v, min(r, flow[i]))) ) {
				flow[i] -= t;
				flow[i^1] += t;
				
				ans += t;
				r -= t;
				if(!r) break;
			}
		}
		return ans;
	}
	int maxflow() {
		int i, ans = 0;
		while(bfs()) {
			memcpy(cur, head, sizeof(cur));
			ans += dfs(S, INF);
		}
		return ans;
	}
}
/////////////////////////////////
int val[MAXN];
int head[MAXN], next[MAXM], tail[MAXM], tid = 1;

int indeg[MAXN], Q[MAXN], qH, qT;
inline void tlink(int u, int v) {
	next[tid] = head[u]; tail[tid] = v; head[u] = tid++;
	dinic::link(v, u, INF);
	indeg[v]++;
}
////////////

int main() {
	freopen("pvz.in", "rt", stdin);
	freopen("pvz.out", "wt", stdout);

	memset(dinic::head, -1, sizeof(dinic::head));
	
	int i, k, r, c, tr, tc, u, v;
	scanf("%d%d", &N, &M);
	for(r=0;r<N;r++) for(c=0;c<M;c++) {
		scanf("%d", &val[plid(r, c)]);
		scanf("%d", &k);
		for(i=0;i<k;i++) {
			scanf("%d%d", &tr, &tc);
			tlink(plid(r, c), plid(tr, tc));
		}
		if(c != 0) tlink(plid(r, c), plid(r, c-1));
	}

	int Tot = 0;
	//Find rings
	qH = qT = 0;
	for(u=0;u<M*N;u++) if(!indeg[u]) Q[qT++] = u;
	while(qH != qT) {
		u = Q[qH++];
		for(i=head[u];i;i=next[i]) {
			v = tail[i];
			if(!--indeg[v]) Q[qT++] = v;
		}
	}

	//remove points on rings
	for(u=0;u<M*N;u++) if(indeg[u]) val[u] = -INF;

	//Link edges
	for(u=0;u<M*N;u++) {
		if(val[u] > 0) dinic::link(S, u, val[u]), Tot += val[u];
		else if(val[u] < 0) dinic::link(u, T, -val[u]);
	}
	//run flow
	printf("%d", Tot - dinic::maxflow());
}