Description：

一个网格图做植物大战僵尸，每个植物有保护位置，僵尸只能从右边来，每个植物有价值，问最多能获得多少价值，价值可以为负数。

$1\le n\le 20,1\le m \le 30$

Solution：

最大权闭合子图，如果要打这个点就必须打掉保护它的点和他前面的点，但是这样可能会连出环，而一个环是肯定打不掉的，于是用 $tarjan$ 求强连通分量，如果有一个强连通分量大小不为一，就缩点，并把点权设为 $-\infty$ ，然后求最大权闭合子图即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<stack>

#include<queue>

#include<vector>

#include<cstring>

using namespace std;

typedef long long ll;

int n,m;

#define MAXN 22

#define MAXM 32

int to(int i,int j){return (i - 1) * m + j;}

#define fi first

#define se second

vector<int> g[MAXN * MAXM];

int val[MAXN * MAXM];

#define MAXE 800010

#define INF 0x3f3f3f3f

int s,t; 

struct edge

{

	int to,nxt,f;

}e[MAXE];

int edgenum = 0;

int lin[MAXN * MAXM];

void add(int a,int b,int f)

{

	e[edgenum].to = b;e[edgenum].f = f;e[edgenum].nxt = lin[a];lin[a] = edgenum;++edgenum;

	e[edgenum].to = a;e[edgenum].f = 0;e[edgenum].nxt = lin[b];lin[b] = edgenum;++edgenum;

	return;

}

int dfn[MAXN * MAXM],low[MAXN * MAXM],tot = 0;

stack<int> st;

bool v[MAXN * MAXM];

int ins[MAXN * MAXM],siz[MAXN * MAXM],scc = 0;

vector<int> cont[MAXN * MAXM];

int pri[MAXN * MAXM];

void tarjan(int k)

{

	dfn[k] = low[k] = ++tot;

	st.push(k);v[k] = true;

	for(int i = 0;i < g[k].size();++i)

	{

		if(dfn[g[k][i]] == 0)

		{

			tarjan(g[k][i]);

			low[k] = min(low[k],low[g[k][i]]);

		}

		else if(v[g[k][i]])low[k] = min(low[k],dfn[g[k][i]]);

	}

	if(dfn[k] == low[k])

	{

		int t;++scc;

		do

		{

			t = st.top();st.pop();v[t] = false;

			ins[t] = scc;++siz[scc];

			cont[scc].push_back(t);

		}while(t != k);

	}

	return;

}

int ch[MAXN * MAXM];

bool check()

{

	queue<int> q;

	q.push(s);

	memset(ch,-1,sizeof(ch));

	ch[s] = 0;

	while(!q.empty())

	{

		int k = q.front();q.pop();

		for(int i = lin[k];i != -1;i = e[i].nxt)

		{

			if(ch[e[i].to] == -1 && e[i].f)

			{

				ch[e[i].to] = ch[k] + 1;

				q.push(e[i].to);

			}

		}

	}

	return (ch[t] != -1);

}

int flow(int k,int f)

{

	if(k == t)return f;

	int r = 0;

	for(int i = lin[k];i != -1 && f > r;i = e[i].nxt)

	{

		if(ch[e[i].to] == ch[k] + 1 && e[i].f)

		{

			int l = flow(e[i].to,min(f - r,e[i].f));

			e[i].f -= l;r += l;e[i ^ 1].f += l;

		}

	}

	if(r == 0)ch[k] = -1;

	return r;

}

int dinic()

{

	ll ans = 0,r;

	while(check())while(r = flow(s,INF))ans += r;

	return ans;

}

int main()

{

	memset(lin,-1,sizeof(lin));

	scanf("%d%d",&n,&m);

	s = n * m + 1;t = s + 1;

	ll sum = 0;

	int k,a,b;

	for(int i = 1;i <= n;++i)

	{

		for(int j = 1;j <= m;++j)

		{

			scanf("%d",&val[to(i,j)]);

			scanf("%d",&k);

			while(k--)

			{

				scanf("%d%d",&a,&b);++a;++b;

				g[to(a,b)].push_back(to(i,j));

			}

			if(j < m)g[to(i,j)].push_back(to(i,j + 1));

		}

	}

	for(int i = 1;i <= t;++i)if(dfn[i] == 0)tarjan(i);

	for(int i = 1;i <= t;++i)

	{

		if(siz[ins[i]] == 1)pri[ins[i]] = val[i];

		else pri[ins[i]] = -INF;

	}

	for(int i = 1;i <= scc;++i)

	{

		if(pri[i] > 0)sum += pri[i];

		if(pri[i] > 0)add(s,i,pri[i]);

		else add(i,t,-pri[i]);

	}

	for(int i = 1;i <= t;++i)

		for(int k = 0;k < g[i].size();++k)

			if(ins[i] != ins[g[i][k]])

				add(ins[i],ins[g[i][k]],INF);

	cout << sum - dinic() << endl;

	return 0;

}