题解 P2805 【[NOI2009]植物大战僵尸】

· · 题解

解法：网络流 - 最大权闭合子图 \times 拓扑排序

感觉大家的题解都没有讲得很清楚呢。

鉴于大家可能会以这道题作为 最大权闭合子图 的入门题，我就在这里给大家讲一些有关的概念，帮助大家快速入门吧！

最大权闭合子图::概念

什么是 闭合子图 ？

  1. 它是一种子图 （逃
  2. 它还是有向图的子图。。
  3. 它还可以一路走到底，不撞南墙不回头。。。

具体来说，就是：对于每个点，从它出发，能够走到的所有点都属于闭合子图中

举个栗子，对于下面这张图， \{b, c, d\} 、 \{b, d\} 都是它的闭合子图。但是 \{a, b, d\} 却不是，因为从 a 可以走到 c ， c 却不在 \{a, b, d\} 中。

\text{形式化地（如果你想看的话），若} G'(V', E') \text{是} G(V, E) \text{的一个闭合子图，那么：}
  1. V' \in V, E' \in E
  2. \forall (u, v) \in E, \text{都有} u \in V' \text{ 且 } v \in V'

最大权闭合子图就是原图中点权和最大的闭合子图。

这个模型有什么用呢？待我慢慢道来。

最大权闭合子图::实现

最大权闭合子图问题可以使用最小割解决OVO！。

连边方式

至于 val[u] = 0 （零权点）的情况，向 S 还是 T 连边对答案并没有影响（见下解释），所以可以不做特判。

如图所示，右边是原图，网络流连边如左图所示。

直接在图上跑最小割即可，最大权 = 正点权和 - 最小割 ，而最大权闭合子图的节点就是与 S 联通的部分。

为什么这样建模是正确的呢？让我们分析一下：

首先，所有不连向 S 或 T 的边容量都是 INF ，不可能被割掉。

这样，能被割掉的边只有连向 S 或 T 的边（这样的割被称为 简单割 ）。

设与 S 联通的节点集为 X ，与 T 联通的节点集为 Y ，那么最大权闭合子图的节点就是 X 集。

一开始假设所有正权点都在（最大权）闭合子图中，

对于某一个正权点 u ，如果割掉它与 S 的连边，意味着将它分到 Y 集合中，不选它作为闭合子图的节点，故闭合子图权值应减去 val[u] 。

对于某一个负权点 u ，如果割掉它与 T 的连边，意味着将它分到 X 集合中，那么闭合子图权值应加上 val[u] ，即减去 -val[u]。

如下图所示，假设这是网络图中的一条路径：

这个图有两种割法，其中割掉蓝色的边花费最小，需要付出 1 的费用。

故这个图中闭合子图的最大权值是 2 - 1 = 1 。

这题跟 最大权闭合子图 有什么关系呢？想必大家已经能够发现一些规律了！

题目分析

规律：

我们看一下题目描述：

对于第r行的进攻，Zombies必须首先攻击Pr, M-1；若需要对Pr, c（0≤c<M-1）攻击，必须将Pr,M-1, Pr, M-2 … Pr, c+1先击溃，并移动到位置(r, c)才可进行攻击。
即便Zombie进入了一个Plant所在的位置，但该位置属于其他植物的攻击位置集合，则Zombie会被瞬间消灭而所在位置的植物则安然无恙

题目描述暗示着： 如果你要攻击植物 i ，那么你就必须把 i 的右边一棵植物、以及保护着它的所有植物都一起攻击掉 。

这与最大权闭合子图中 对于每个点，从它出发，能够走到的所有点都属于闭合子图中 刚好契合。

我们可以这样建图：

  1. 植物 i 的点权设为 val[i]
  2. 所有植物 i 向它的右边连边
  3. 如果一个植物 j 保护着 i ， i 向 j 连边

在这个图上求出最大权闭合子图，答案就是最大收益，也就是问题的答案。

一个问题

等等，如果你直接写出代码，你会发现你只能拿到可怜的分数（甚至连样例都过不了）

我们漏了一种情况，如果两棵植物互相保护（环），那么僵尸无论如何都无法攻击到它们。

（上面这个图展示的是节点之间的保护关系，事实上在网络图中，边刚好相反）

同理，被环所保护的节点也无法被攻击到。

所有出现在环中以及被环保护的节点都应该被去除。我们可以先建一个反向图（这里是指相对于网络图的反向图），并进行拓扑排序，能够被拓扑排序遍历到的节点才能用来建图。

讲到这里，问题终于解决了！

代码

激动人心的代码时刻！（假的，写得超丑 2333 ）

#include<bits/stdc++.h>
using namespace std;
#define POINT(X, Y)  ((X) * 31 + (Y))
const int MAXN = POINT(30, 30) + 10;
const int INF = 2000000000;
const int MAXM = MAXN * MAXN + 10;
struct Graph {
    struct Node {
        int to, cap;
        int next;
    } node[MAXM * 2];
    int top, head[MAXN];
    Graph() {
        top = 1;
    }
    void add(int u, int v, int cap) {
        top ++;
        node[top].to = v;
        node[top].cap = cap;
        node[top].next = head[u];
        head[u] = top;
        top ++;
        node[top].to = u;
        node[top].cap = 0;
        node[top].next = head[v];
        head[v] = top;
    }
    queue<int> Q;
    int dis[MAXN];
    int s, t;
    bool bfs() {
        memset(dis, -1, sizeof(dis));
        dis[s] = 0;
        Q.push(s);
        while(!Q.empty()) {
            int u = Q.front();
            Q.pop();
            for(int i = head[u]; i; i = node[i].next) {
                int v = node[i].to;
                if(dis[v] == -1 && node[i].cap) {
                    dis[v] = dis[u] + 1;
                    Q.push(v);
                }
            }
        }
        return dis[t] != -1;
    }
    int dfs(int u, int flow) {
        if(u == t)
            return flow;
        else {
            int ret = flow;
            for(int i = head[u]; i && ret; i = node[i].next) {
                int v = node[i].to;
                if(dis[v] == dis[u] + 1 && node[i].cap) {
                    int k = dfs(v, min(ret, node[i].cap));
                    node[i].cap -= k;
                    node[i ^ 1].cap += k;
                    ret -= k;
                }
            }
            if(ret == flow)
                dis[u] = -1;
            return flow - ret;
        }
    }
    int dinic() {
        int ans = 0;
        while(bfs())
            ans += dfs(s, INF);
        return ans;
    }
} G;
int n, m;
int score[MAXN];
vector<int> out[MAXN];
int in[MAXN];
bool vis[MAXN];
queue<int> Q;
void toposort() {
    for(int i = 1; i <= n; i ++) {
        for(int j = 1; j <= m; j ++) {
            if(!in[POINT(i, j)]) {
                Q.push(POINT(i, j));
                vis[POINT(i, j)] = true;
            }
        }
    }
    while(!Q.empty()) {
        int u = Q.front();
        Q.pop();
        for(int i = 0; i < out[u].size(); i ++) {
            int v = out[u][i];
            in[v] --;
            if(!vis[v] && !in[v]) {
                Q.push(v);
                vis[v] = true;
            }
        }
    }
}
int main() {
    cin>>n>>m;
    for(int i = 1; i <= n; i ++) {
        for(int j = 1; j <= m; j ++) {
            int cnt;  //  保护植物的棵数
            cin>>score[POINT(i, j)]>>cnt;
            for(int k = 1; k <= cnt; k ++) {
                int x, y;
                cin>>x>>y;
                //  POINT(i, j) <- POINT(x, y)
                x ++;
                y ++;
                out[POINT(i, j)].push_back(POINT(x, y));
                in[POINT(x, y)] ++;
            }
            if(j < m) {
                out[POINT(i, j + 1)].push_back(POINT(i, j));
                in[POINT(i, j)] ++;
            }
        }
    }
    toposort();
    G.s = MAXN - 1;
    G.t = MAXN - 2;
    int sum = 0;
    for(int i = 1; i <= n; i ++) {
        for(int j = 1; j <= m; j ++) {
            int u = POINT(i, j);
            if(!vis[u])
                continue;
            if(score[u] >= 0) {
                G.add(G.s, u, score[u]);
                sum += score[u];
                // printf("S -> [%d, %d] : %d\n", i, j, score[u]);
            }
            else {
                G.add(u, G.t, -score[u]);
                // printf("[%d, %d] -> T : %d\n", i, j, -score[u]);
            }
            for(int k = 0; k < out[u].size(); k ++) {
                int v = out[u][k];
                if(vis[v]) {
                    G.add(v, u, INF);
                    // printf("[%d, %d] -> [%d, %d] : INF\n", v / 31, v % 31, i, j);
                }
            }
        }
    }
    cout<<sum - G.dinic()<<endl;
    return 0;
}

内容会陆续搬运到博客里......