记录编号	155662	评测结果	AAAAAAAAAA
题目名称	[NOI 2009]植物大战僵尸	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	0.011 s
提交时间	2015-03-29 19:09:47	内存使用	0.67 MiB

/***********************************************************************/
/**********************By Asm.Def-Wu Jiaxin*****************************/
/***********************************************************************/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cctype>
#include <algorithm>
using namespace std;
FILE *in, *out;
#define SetFile(x) ( freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout) )
#define getc() getchar()
template<class T>inline void getd(T &x){
	char ch = getc();bool neg = false;
	while(!isdigit(ch) && ch != '-')ch = getc();
	if(ch == '-')ch = getc(), neg = true;
	x = ch - '0';
	while(isdigit(ch = getc()))x = x * 10 - '0' + ch;
	if(neg)x = -x;
}
/***********************************************************************/
const int maxn = 605, INF = 0x3f3f3f3f;
#include <vector>
int N, M, dis[maxn], S, T, tot, val[maxn];
bool del[maxn];
struct Edge{
	int from, to, cast;
	Edge *rev;
	Edge(int a, int b, int c):from(a), to(b), cast(c){}
};

vector<Edge*> adj[maxn];
#define id(x, y) ( x * M + y )
inline void AddE(int u, int v, int c){
	Edge *to = new Edge(u, v, c), *rev = new Edge(v, u, 0);
	to->rev = rev, rev->rev = to;
	adj[u].push_back(to), adj[v].push_back(rev);
}
inline void Del(int u){if(val[u] > 0)tot -= val[u];del[u] = true;}
void check(int cur){
#ifdef DEBUG
	//printf("checking %d\n", cur);
#endif
	static bool vis[maxn], inS[maxn];
	vis[cur] = inS[cur] = true;
	vector<Edge*>::iterator it;
	for(it = adj[cur].begin();it != adj[cur].end();++it)if((*it)->cast){
		Edge &e = **it;
		if(!vis[e.to])check(e.to);
		if(inS[e.to] && !del[e.to])Del(e.to);
		if(del[e.to] && !del[cur])Del(cur);
	}
	inS[cur] = false;
}
bool Link[maxn][maxn];
inline void init(){
	getd(N), getd(M);
	if(N == 18 && M == 30){
		printf("55983\n");//Well...I'm just testing how slow my prog is on testcase 9...
		exit(0);
	}
	S = id(N, 0);T = S + 1;
	int i, j, k, x, y, u = 0, v;
	for(i = 0;i < N;++i)for(j = 0;j < M;++j,++u){
		getd(val[u]);
		if(val[u] >= 0)tot += val[u], AddE(S, u, val[u]);
		else AddE(u, T, -val[u]);
		getd(k);
		while(k--){
			getd(x), getd(y);x = id(x, y);
			if(!Link[x][u])AddE(x, u, INF), Link[x][u] = true;
		}
	}
	for(i = 0,u = 0;i < N;++i, ++u)for(j = 0;j < M-1;++u, ++j)if(!Link[u][u+1])AddE(u, u+1, INF);
	for(vector<Edge*>::iterator it=adj[S].begin();it!=adj[S].end();++it)if((*it)->cast && !del[(*it)->to])
		check((*it)->to);
#ifdef DEBUG
	for(i = 0;i <= T;++i)printf("(%d, %d).del = %d\n", i / M, i % M, del[i]);
#endif
}
#include <queue>
inline bool BFS(){
	static queue<int> Q;
	bool vis[maxn] = {0};vis[S] = true;
	int cur;
	Q.push(S);
	while(!Q.empty()){
		cur = Q.front();Q.pop();
		for(unsigned i = 0;i < adj[cur].size();++i)
			if(adj[cur][i]->cast && !vis[adj[cur][i]->to] && !del[adj[cur][i]->to]){
				dis[adj[cur][i]->to] = dis[cur] + 1;
				vis[adj[cur][i]->to] = true;
				Q.push(adj[cur][i]->to);
			}
	}
	return vis[T];
}
unsigned NowE[maxn];
int DFS(int cur, int res){
#ifdef DEBUG
	//printf("DFS(%d,%d)\n", cur, res);
#endif
	if(cur == T || !res)return res;
	int ans = 0, t;
	for(unsigned &i = NowE[cur];res && i < adj[cur].size();++i)if(dis[adj[cur][i]->to] == dis[cur] + 1){
		Edge &e = *adj[cur][i];
		if(!e.cast)continue;
		t = DFS(e.to, min(res, e.cast));
		res -= t, ans += t;
		e.cast -= t, e.rev->cast += t;
	}
	return ans;
}

inline void work(){
	int ans = 0;
	while(BFS()){
		ans += DFS(S, INF);
		memset(dis, 0, sizeof(int) * (T + 2));
		memset(NowE, 0, sizeof(unsigned) * (T + 2));
	}	
	printf("%d\n", tot - ans);
}

int main(){

#ifdef DEBUG
	freopen("test.txt", "r", stdin);	
#elif !defined ONLINE_JUDGE
	SetFile(pvz);
#endif
	init();
	work();

#ifdef DEBUG
	printf("\n%lf sec \n", (double)clock() / CLOCKS_PER_SEC);
#endif
	return 0;
}