NOI2009[植物大战僵尸/pvz]

恩，在做题的时候玩了一次植物大战僵尸。

然后，这道题是最大权闭合图。

还有注意将一定不会被攻击的植物从图中丢掉。

推荐读一下2007年国家集训队论文（胡伯涛《最小割模型在信息学竞赛中的应用》）。

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;

}