题目描述

Description

Plants vs. Zombies（PVZ）是最近十分风靡的一款小游戏。Plants（植物）和Zombies（僵尸）是游戏的主角，其中：Plants防守，而Zombies进攻。该款游戏包含多种不同的挑战系列，比如Protect Your Brain、Bowling等等。其中最为经典的，莫过于玩家通过控制Plants来防守Zombies的进攻，或者相反地由玩家通过控制Zombies对Plants发起进攻。

现在，我们将要考虑的问题是游戏中Zombies对Plants的进攻，请注意，本题中规则与实际游戏有所不同。游戏中有两种角色，Plants和Zombies，每个Plant有一个攻击位置集合，它可以对这些位置进行保护；而Zombie进攻植物的方式是走到植物所在的位置上并将其吃掉。

游戏的地图可以抽象为一个N行M列的矩阵，行从上到下用0到N-1编号，列从左到右用0到M-1编号；在地图的每个位置上都放有一个Plant，为简单起见，我们把位于第r行第c列的植物记为Pr，c。

Plants分很多种，有攻击类、防守类和经济类等等。为了简单的描述每个Plant，定义Score和Attack如下：
Score[Pr，c]
Zombie击溃植物Pr，c可获得的能源。若Score[Pr，c]为非负整数，则表示击溃植物Pr，c可获得能源Score[Pr，c]，若为负数表示击溃Pr，c需要付出能源-Score[Pr，c]。
Attack[Pr，c]
植物Pr，c能够对Zombie进行攻击的位置集合。
Zombies必须从地图的右侧进入，且只能沿着水平方向进行移动。Zombies攻击植物的唯一方式就是走到该植物所在的位置并将植物吃掉。因此Zombies的进攻总是从地图的右侧开始。也就是说，对于第r行的进攻，Zombies必须首先攻击Pr，M-1；若需要对Pr，c（0<=c < M-1）攻击，必须将Pr，M-1，Pr，M-2，…，Pr，c+1先击溃，并移动到位置（r，c）才可进行攻击。
在本题的设定中，Plants的攻击力是无穷大的，一旦Zombie进入某个Plant的攻击位置，该Zombie会被瞬间消灭，而该Zombie没有时间进行任何攻击操作。因此，即便Zombie进入了一个Plant所在的位置，但该位置属于其他植物的攻击位置集合，则Zombie会被瞬间消灭而所在位置的植物则安然无恙（在我们的设定中，Plant的攻击位置不包含自身所在位置，否则你就不可能击溃它了）。
Zombies的目标是对Plants的阵地发起进攻并获得最大的能源收入。每一次，你可以选择一个可进攻的植物进行攻击。本题的目标为，制定一套Zombies的进攻方案，选择进攻哪些植物以及进攻的顺序，从而获得最大的能源收入。

Input

输入文件中的第一行为两个整数N，M，分别表示地图的行数和列数。
接下来的N×M行，描述了每个位置上植物的信息。其中：第r×M+c+1行按照如下格式给出植物Pr，c的信息：第一个整数为Score[Pr，c]，第二个整数为集合Attack[Pr，c]中的位置个数w，接下来为w个位置信息（r'，c'），表示Pr，c可以攻击位置第r'行第c'列。

Output

输出文件中仅一行为一个整数，表示可以获得的最大能源收入。
注意：你也可以选择不进行任何攻击，这样能源收入为0。

Sample Input

3 2
10 0
20 0
-10 0
-5 1 0 0
100 1 2 1
100 0

Sample Output

25

HINT

【样例说明】
在样例中，植物P1，1可以攻击位置（0，0），P2，0可以攻击位置（2，1）。
一个方案为，首先进攻P1，1，P0，1，此时可以攻击P0，0。共得到能源收益为：(-5)+20+10=25。
注意：位置（2，1）被植物P2，0保护，所以无法攻击第2行中的任何植物。
【数据规模和约定】
对于20%的数据，满足：1<=N，M<=5；
对于40%的数据，满足：1<=N，M<=10；
对于100%的数据，满足：1<=N<=20，1<=M<=30，-10000<=Score<=10000。

题目分析

吃掉一棵植物可以获得收益或付出代价
就是最大权闭合子图嘛= =
并且这题还比较蛇皮 环不能吃
所以我们先跑一边topsort即可

s连正权值点 流量为权值
负权值点连t 流量为权值绝对值
i向i+1连边 流量为inf
能保护到的位置向本身连边 流量inf

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
#define V 2333
#define E 2333333
using namespace std;
int n,m,s,t,tot,sum;
int dis[2333],in[2333];
int head[2333],net[2333333],to[2333333],val[2333333],v[2333];
void add(int x,int y,int c)
{
    in[x]++;
    net[++tot]=head[x],head[x]=tot,to[tot]=y,val[tot]=c;
    net[++tot]=head[y],head[y]=tot,to[tot]=x,val[tot]=0;
}
bool visit[23333];
void topsort()
{
    queue<int>q;
    for(int i=0;i<=n*m+1;i++)
        if(!in[i]) q.push(i);
    while(q.size())
    {
        int x=q.front();
        visit[x]=1;
        q.pop();
        if(v[x]>0) sum+=v[x];
        for(int i=head[x];i;i=net[i])
            if((i&1)&&(--in[to[i]])==0) q.push(to[i]);
    }
}
bool vis[23333];
int bfs()
{
    memset(dis,0,sizeof dis);
    queue<int>q;
    q.push(s);
    dis[s]=1;
    while(q.size())
    {
        int x=q.front();
        q.pop();
        for(int i=head[x];i;i=net[i])
            if(val[i]>0&&visit[to[i]]&&!dis[to[i]])
            {
                dis[to[i]]=dis[x]+1;
                q.push(to[i]);
                if(to[i]==t) return 1; 
            }
    }
    return 0;
}
int dinic(int x,int flow)
{
    int tmp,temp=flow;
    if(x==t) return flow;
    for(int i=head[x];i;i=net[i])
        if(val[i]>0&&dis[to[i]]==dis[x]+1&&visit[to[i]])
        {
            tmp=dinic(to[i],min(val[i],temp));
            if(tmp==0) dis[to[i]]=0;
            temp-=tmp,val[i]-=tmp,val[i^1]+=tmp;
            if(!temp) break;
        }
    return flow-temp;
}
int main()
{
    scanf("%d%d",&n,&m);
    s=0,t=n*m+1,tot=1;
    for(int w,i=1;i<=n*m;i++)
    {
        scanf("%d%d",&v[i],&w);
        if(v[i]>0) add(s,i,v[i]);
        else add(i,t,-v[i]);
        if(i%m) add(i,i+1,1<<30);
        while(w--)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            add(x*m+y+1,i,1<<30);
        }
    }
    topsort();
    while(bfs()) sum-=dinic(s,1<<30);
    printf("%d",sum);
    return 0;
}