bzoj - 1565

Posted by WildCow on May 11, 2018

[NOI2009]植物大战僵尸

Time Limit: 10 S
Memory Limit: 64 MB

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’ 列。 1 ≤ N ≤ 20,1 ≤ M ≤ 30,-10000 ≤ Score ≤ 10000 。

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行中的任何植物。


这题题意太鬼畜了
输入我就看半天
给你一个 n * m 的矩阵
每个位置上都有植物
每个植物都有他的价值(可以为负)
每个植物都有若干个他保护的位置坐标(不能保护自身所在的坐标)
如果一个坐标被一个植物保护
那么你一到达这个地方就会马上被消灭
除非你干掉所有保护这个坐标的植物
同时如果一个坐标被保护且这个坐标上有植物
那么你要先把保护这个坐标的植物干掉
你才能获得这个坐标上的植物的价值
所以会出现两个植物互相 py 互相保护最后你哪个的价值都没法获得的情况
同时你每次只能从每行的最右边出发往左走
然后你可以随时换过一行从右重新开始走
不能跳跃
被吃掉的植物不能重生
每行可以走很多次

qnmlgb 老子不描述题意了

刚开始的时候很容易想到的一个建图
每个位置都往自己左边的位置连一条有向边
然后每个位置都往自己保护的位置连一条有向边
然后开始吃瓜
但是我们反过来
要吃一个植物,就必须把保护他的植物或者排在他前面的植物给吃了
所以我们把之前建的图的边都反过来
就会发现一个最大权闭合子图的模型!
同时很明显所有成环的点都不可以到达
一次拓扑排序或者一次 tarjan 把环都拆了
把板子丢上去就 A 了= =


#include <bits/stdc++.h>
using namespace std;

const int N = 650;
const int INF = 0x3f3f3f3f;

struct Node
{
    int to;
    int w;
    int ne;
};

Node node1[N * N];
Node node2[N * N * 2];
int n, m;
int ss, tt;
int cnt;
int top;
int sum;
int cur[N * N * 2]; /// 前向弧优化
int Q[N];
int di[N];
int ma[N];
int head1[N];
int head2[N];
int inde[N];
int St[N];
int del[N];
int vis[N];

void ini1()
{
    top = 0;
    memset(head1, -1, sizeof(head1));
}

void ini2()
{
    top = 0;
    memset(head2, -1, sizeof(head2));
}

void add_edge1(int from, int to)
{
    node1[top].to = to;
    node1[top].ne = head1[from];
    head1[from] = top;
    top ++;
}

void add_edge2(int from, int to, int w)
{
    node2[top].to = to;
    node2[top].w = w;
    node2[top].ne = head2[from];
    head2[from] = top;
    top ++;
}

void Topology()
{
    int li;
    int Stop;

    li = n * m;
    Stop= 0;
    memset(vis, 0, sizeof(vis));
    for(int i = 0; i < li; i ++){
        if(!inde[i]){
            St[Stop] = i;
            Stop++;
        }
        else{
            del[i] = 1;
        }
    }
    while(Stop){
        int now;

        now = St[Stop- 1];
        Stop--;
        del[now] = 0;
        for(int i = head1[now]; i != -1; i = node1[i].ne){
            inde[node1[i].to] --;
            if(!inde[node1[i].to]){
                St[Stop] = node1[i].to;
                Stop++;
            }
        }
    }
}
bool build()
{
    int l, r;
    int now;

    memset(di, 0, sizeof(di));
    di[ss] = 1;
    l = r = 0;
    Q[r] = ss;
    r ++;
    while(l != r){
        now = Q[l];
        l ++;
        if(now == tt){
            return true;
        }
        for(int i = head2[now]; i != -1; i = node2[i].ne){
            int v, w;

            v = node2[i].to;
            w = node2[i].w;
            if(w && !di[v]){
                di[v] = di[now] + 1;
                Q[r] = v;
                r ++;
            }
        }
    }

    return false;
}

int dfs(int u, int maxf)
{
    int ans;

    if(u == tt){
        return maxf;
    }
    ans = 0;
    for(int &i = cur[u]; i != -1; i = node2[i].ne){
        int v, w;

        v = node2[i].to;
        w = node2[i].w;
        if(w && di[v] == di[u] + 1){
            int t;

            t = dfs(v, min(maxf - ans, w));
            node2[i].w -= t;
            node2[i ^ 1].w += t;
            ans += t;
            if(ans == maxf){
                return ans;
            }
        }
    }
    if(!ans){
        di[u] = -2;
    }

    return ans;
}

int Dinic()
{
    int ans;

    ans = 0;
    while(build()){
        for(int i = 0; i <= tt; i ++){
            cur[i] = head2[i];
        }
        ans += dfs(ss, INF);
        // cout << ans << endl;
    }

    return ans;
}

int main(int argc, char const *argv[])
{
    int li;

    while(scanf("%d%d", &n, &m) == 2){
        cnt = 0;
        sum = 0;
        ss = n * m;
        tt = ss + 1;
        ini1();
        for(int i = 0; i < n; i ++){
            for(int j = 0; j < m; j ++){
                int t;

                scanf("%d%d", &ma[cnt], &t);
                for(int k = 0; k < t; k ++){
                    int x, y;

                    scanf("%d%d", &x, &y);
                    add_edge1(cnt, x * m + y);
                    inde[x * m + y] ++;
                }
                if(j){
                    add_edge1(cnt, cnt - 1);
                    inde[cnt - 1] ++;
                }
                cnt ++;
            }
        }
        /// cout << 666 << endl;
        Topology();
        ini2();
        li = n * m;
//        for(int i = 0; i < li; i ++){
//            if(del[i]){
//                cout << i << endl;
//            }
//        }
        for(int i = 0; i < li; i ++){
            if(!del[i]){
                if(ma[i] > 0){
                    sum += ma[i];
                    add_edge2(ss, i, ma[i]);
                    add_edge2(i, ss, 0);
                    // printf("%d -> %d = %d\n", ss, i, ma[i]);
                }
                else{
                    add_edge2(i, tt, -ma[i]);
                    add_edge2(tt, i, 0);

                    // printf("%d -> %d = %d\n", i, tt, -ma[i]);
                }
                for(int j = head1[i]; j != -1; j = node1[j].ne){
                    if(!del[node1[j].to]){
                        add_edge2(node1[j].to, i, INF);
                        // printf("%d -> %d\n", node1[j].to, i);
                        add_edge2(i, node1[j].to, 0);
                    }
                }
            }
        }
        printf("%d\n", sum - Dinic());
    }

    return 0;
}