# NOI2009[植物大战僵尸/pvz]

CODE:

/*

PROGRAM: \$PROGRAM

AUTHOR: Su Jiao

DATE: 2010-4-28

DESCRIPTION:

\$DESCRIPTION

*/

#include <stdio.h>

#include <string.h>

#include <vector>

#include <queue>

using std::vector;

#define P std::pair<int,int>

#define Q std::priority_queue<P>

#define min(a,b) ((a)<(b)?(a):(b))

#define max(a,b) ((a)>(b)?(a):(b))

const int MAXN=20+1,MAXM=30+1,oo=~(1<<31);

int N,M;

int score[MAXN*MAXM];

vector<int> protect[MAXN*MAXM];

int c[MAXN*MAXM+2][MAXN*MAXM+2];

bool can_attack[MAXN*MAXM+2];

int indegree[MAXN*MAXM+2];

void get_attack()

{

for (int i=0;i<N*M;i++)

for (int j=0;j<protect[i].size();j++)

indegree[protect[i][j]]++;

int open=0,close=0;

int q[MAXN*MAXM+2];

for (int i=0;i<N*M;i++)

if (!indegree[i])

q[open++]=i;

while (close<open)

{

can_attack[q[close]]=true;

for (int j=0;j<protect[q[close]].size();j++)

{

indegree[protect[q[close]][j]]–;

if (!indegree[protect[q[close]][j]])

q[open++]=protect[q[close]][j];

}

close++;

}

}

int h[MAXN*MAXM+2],vh[MAXN*MAXM+2];

int n,augc;

int flow;

bool found;

void aug(int m)

{

int i,augco,minh;

minh=n-1;

augco=augc;

if (m==n)

{

found=true;

flow+=augc;

return;

}

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

if (c[m][i]>0)

{

if (h[m]==h[i]+1)

{

if (c[m][i]<augc) augc=c[m][i];

aug(i);

if (h[1]>=n) return;

if (found) break;

augc=augco;

}

if (h[i]<minh) minh=h[i];

}

if (!found)

{

vh[h[m]]–;

if (vh[h[m]]==0) h[1]=n;

h[m]=minh+1;

vh[h[m]]++;

}

else

{

c[m][i]-=augc;

c[i][m]+=augc;

}

}

int max_flow(int S,int T) //SAP

{

int d[MAXN*MAXM+2][MAXN*MAXM+2];

memcpy(d,c,sizeof(d));

n=N*M+2;

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

{

if (i!=0&&i!=S)

{

d[i][0]=c[i][S];

d[0][i]=c[S][i];

d[i][S]=c[i][0];

d[S][i]=c[0][i];

}

}

d[S][0]=c[0][S];

d[0][S]=c[S][0];

d[0][0]=c[S][S];

d[S][S]=c[0][0];

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

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

c[i][j]=d[i-1][j-1];

vh[0]=n;

while (h[1]<n)

{

augc=oo;

found=false;

aug(1);

}

return flow;

}

/*

int max_flow(int S,int T) //preflow-push

{

const int L=0,R=N*M+1;

static int flow=0;

static int f[MAXN*MAXM+2][MAXN*MAXM+2];

//memset(f,0,sizeof(f));

static int h[MAXN*MAXM+2];

//BFS

{

static int open=0,close=0;

static int q[MAXN*MAXM+2];

static bool inq[MAXN*MAXM+2];

//memset(inq,0,sizeof(inq));

inq[q[open++]=T]=true;

h[T]=0;

while (close<open)

{

int now=q[close++];

for (int next=L;next<=R;next++)

if ((f[next][now]<c[next][now])&&(!inq[next]))

{

inq[q[open++]=next]=true;

h[next]=h[now]+1;

//printf(“h[%d(next)]=%d\n”,next,h[next]);

}

}

}

h[S]=N*M+2;

static int e[MAXN*MAXM+2];

//memset(e,0,sizeof(e));

for (int i=L;i<=R;i++)

if (f[S][i]<c[S][i])

{

e[i]+=c[S][i];

f[S][i]+=c[S][i];

f[i][S]-=c[S][i];

e[S]-=c[S][i];

}

for (;;)

{

bool find=false;

for (int i=L;i<=R;i++)

if (e[i]>0&&i!=S&&i!=T)

{

find=true;

for (int j=L;j<=R;j++)

if (h[i]==h[j]+1&&f[i][j]<c[i][j])

{

//Push

int p=min(e[i],c[i][j]-f[i][j]);

//printf(“push(%d,%d) :%d\n”,i,j,p);

e[j]+=p;

f[i][j]+=p;

f[j][i]-=p;

e[i]-=p;

}

if (e[i])

{

int minh=h[i];

for (int j=L;j<=R;j++)

if (f[i][j]<c[i][j])

minh=min(minh,h[j]);

h[i]=minh+1;

}

}

if (!find) break;

}

flow=e[T];

//printf(“flow:%d\n”,flow);

return flow;

}

*/

/*

int max_flow(int S,int T) //shortest-augument

{

int L=0,R=N*M+1;

int flow=0;

int f[MAXN*MAXM+2][MAXN*MAXM+2];

memset(f,0,sizeof(f));

int d[MAXN*MAXM+2];

//BFS

{

int open=0,close=0;

int q[MAXN*MAXM+2];

bool inq[MAXN*MAXM+2];

memset(inq,0,sizeof(inq));

inq[q[open++]=T]=true;

d[T]=0;

while (close<open)

{

int now=q[close++];

for (int next=L;next<=R;next++)

if ((f[next][now]<c[next][now])&&(!inq[next]))

{

inq[q[open++]=next]=true;

d[next]=d[now]+1;

}

}

}

int pre[MAXN*MAXM+2];

int i=S,j;

while (d[S]<M*N+2)

{

bool find=false;

for (j=L;j<=R;j++)

if (f[i][j]<c[i][j]&&d[i]==d[j]+1)

{

find=true;

break;

}

if (find)

{

pre[j]=i;

i=j;

if (i==T)

{

int inc=oo;

int u;

u=T;

do

{

inc=min(inc,c[pre[u]][u]-f[pre[u]][u]);

u=pre[u];

}

while (u!=S);

flow+=inc;

u=T;

do

{

f[pre[u]][u]+=inc;

f[u][pre[u]]-=inc;

u=pre[u];

}

while (u!=S);

i=S;

}

}

else

{

d[i]=N*M+2;

for (j=L;j<=R;j++)

if (f[i][j]<c[i][j])

d[i]=min(d[i],d[j]+1);

if (i!=S) i=pre[i];

}

}

//printf(“flow:%d\n”,flow);

return flow;

}

*/

/*

int max_flow(int S,int T) //Edmonds-Karp + Priority Queue

{

int L=0,R=N*M+1;

int flow=0;

int f[MAXN*MAXM+2][MAXN*MAXM+2];

memset(f,0,sizeof(f));

for (;;)

{

Q q;

bool inq[MAXN*MAXM+2];

memset(inq,0,sizeof(inq));

int val[MAXN*MAXM+2];

int pre[MAXN*MAXM+2];

val[S]=oo;

pre[S]=S;

q.push(P(val[S],S));

inq[S]=true;

while ((!inq[T])&&(!q.empty()))

{

int now=q.top().second;

q.pop();

for (int next=L;next<=R;next++)

if ((f[now][next]<c[now][next])&&(!inq[next]))

{

val[next]=min(val[now],c[now][next]-f[now][next]);

pre[next]=now;

q.push(P(val[next],next));

inq[next]=true;

}

}

if (inq[T])

{

flow+=val[T];

int u=T;

while (pre[u]!=u)

{

f[pre[u]][u]+=val[T];

f[u][pre[u]]-=val[T];

u=pre[u];

}

}

else break;

}

//printf(“flow:%d\n”,flow);

return flow;

}

*/

/*

int max_flow(int S,int T) //Edmonds-Karp

{

int L=0,R=N*M+1;

int flow=0;

int f[MAXN*MAXM+2][MAXN*MAXM+2];

memset(f,0,sizeof(f));

for (;;)

{

int open=0,close=0;

int q[MAXN*MAXM+2];

bool inq[MAXN*MAXM+2];

memset(inq,0,sizeof(inq));

int val[MAXN*MAXM+2];

int pre[MAXN*MAXM+2];

inq[q[open++]=S]=true;

val[S]=oo;

pre[S]=S;

while (!inq[T]&&(close<open))

{

int now=q[close++];

for (int next=L;next<=R;next++)

if ((f[now][next]<c[now][next])&&(!inq[next]))

{

inq[q[open++]=next]=true;

val[next]=min(val[now],c[now][next]-f[now][next]);

pre[next]=now;

if (next==T) break;

}

}

if (inq[T])

{

flow+=val[T];

int u=T;

while (pre[u]!=u)

{

f[pre[u]][u]+=val[T];

f[u][pre[u]]-=val[T];

u=pre[u];

}

}

else break;

}

//printf(“flow:%d\n”,flow);

return flow;

}

*/

int main()

{

freopen(“pvz.in”,“r”,stdin);

freopen(“pvz.out”,“w”,stdout);

scanf(“%d%d”,&N,&M);

for (int i=0;i<N*M;i++)

{

int r,c,p;

scanf(“%d”,score+i);

r=i/M;

c=i%M;

if (c>0) protect[i].push_back(r*M+c-1);

scanf(“%d”,&p);

while (p–)

{

scanf(“%d%d”,&r,&c);

protect[i].push_back(r*M+c);

}

}

get_attack();

int total=0;

int S=N*M,T=N*M+1;

for (int i=0;i<M*N;i++)

{

if (can_attack[i]&&score[i]>0)

total+=(c[S][i]=score[i]);

else if (can_attack[i]&&score[i]<0)

c[i][T]=-score[i];

}

for (int i=0;i<M*N;i++)

for (int j=0;j<protect[i].size();j++)

if (can_attack[i]&&can_attack[protect[i][j]])

c[protect[i][j]][i]=oo;

printf(“%d\n”,total-max_flow(S,T));

fclose(stdin);

fclose(stdout);

return 0;

}