BZOJ 1565 - [NOI2009]植物大战僵尸

#最大权闭合子图 #最小割 #网络流

Published on 2016-04-06

描述

样例输入

样例输出

分析

本体是最大权闭合子图的应用，什么是闭合图呢？

闭合图：定义一个有向图 $G = (V , E)$ 的闭合图，是该有向图的一个点集,且该点集的所有出边都还指向该点集。即闭合图内的任意点的任意后继也一定在闭合图中。更形式化地说，闭合图是这样的一个点集 $V ' \in V$ ,满足对于引出的，必有 $v \in V '$ 成立。按照上面的定义,闭合图是允许超过一个连通块的。

在许多实际应用中，给出的有向图常常是一个有向无环图(DAG),闭合图的性质恰好反映了事件间的必要条件的关系：一个事件的发生,它所需要的所有前提也都要发生。一个常见的例子就是制定大学的选课计划,其中一些课程需要以另一些课程为基础，这就是给出了有向无环图。若给所有课程打分,最大权闭合图对应了获益最大或效率最高的选课计划,解决了这个问题,就可以容易地选出一个最合理的选课计划。

对应到本题，吃掉一个植物是有收益/代价的，同时，吃掉一个植物必须吃掉所有保护它的植物，即攻击该植物所在位置的植物和在该植物前面的植物，这就是前提。我们要最大化收益，用最小割解决。
如果我们选择吃掉的植物集合为 $S$ 的话，总收益 $W$ 是

W = \sum_{i\in S} \text{Score}_i = \sum _{i\in s, \text{Score}_i \ge 0} \text{Score}_i - \sum _{i\in s, \text{Score}_i < 0}\text{Score}_i

这样是没法用最小割最小化的，转换一下：

显然最大化括号中的式子即可。那么考虑建图：
新建源点汇点 $s, t$ ，对于每个植物 $P_i$ ，如果 $S_i$ 大于 0，连边 $(s, P_i, S_i)$ ；如果 $S_i$ 小于 0，连边 $(P_i, t, -S_i)$ 。如果植物 $P_j$ 保护 $P_i$ ，连边 $(P_i, P_j, +\infty)$ 。
答案是用所有正权值的和减去最小割就是了。

上面的图在保护关系有环的情况下是不对的，因为最大权闭合子图无法处理环，先不考虑环，看看这个图。
显然在最小割中，与 $S$ 联通的点是要打的，与 $T$ 联通的点是不打的（难以理解可以考虑所有植物到源汇都有流量为 0 的边）。那么对于正植物来说，不打，就要割到源点的边，花费 $\text{Score}_i$ ，正好对应中的一项；对于负植物，打，就要割到汇点的边，花费 $\text{Score}_i$ ，正好对应 $\sum _{i\in s, \text{Score}_i < 0}\text{Score}_i$ 中的一项。
再看保护关系，如果植物 $P_j$ 保护 $P_i$ ，那么要打 $P_i$ ， $P_j$ 必须先打，不成立的只有打 $P_i$ 却不打 $P_j$ 的情况，如果出现这样的情况，由于有无穷边，显然有新的增广路，故不会出现这种情况。

现在我们知道在无环的时候都是对的，那么有环会怎么样呢？考虑 $P_i$ 保护 $P_j$ ， $P_j$ 保护 $P_i$ ，那么它们谁都不能打，如果刚刚的建图方法，则 $P_i, P_j$ 之间有无向边，发现它们都打是合法的，显然不对。
所以如果保护关系有环，图是不对的，如何避免呢？先不连网络流中的保护关系边，我们对保护关系建图，如果 $P_j$ 保护 $P_i$ ，连有向边 $(P_j, P_i)$ ，我们发现，所有环都不能选，从环出发能到的所有点也不能选，所以我们拓扑排序，所有没访问的点都是不能选的。
再次遍历保护关系，如果 $P_j$ 保护 $P_i$ 且都是访问过的点，那么网络流中加边 $(P_i, P_j, +\infty)$ 。同时对所有未访问的点 $P_i$ ，连边 $(P_i, t, +\infty)$ 表示排除了选择的可能，再跑网络流，用正收益之和减去流量即可！

代码

//  Created by Sengxian on 4/5/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//    BZOJ 1565 网络流
#include <algorithm>
#include <iostream>
#include <cctype>
#include <cassert>
#include <climits>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

inline int ReadInt() {
    static int n, ch;
    static bool flag;
    n = 0, ch = getchar(), flag = false;
    while (!isdigit(ch)) flag |= ch == '-', ch = getchar();
    while (isdigit(ch)) n = (n << 1) + (n << 3) + ch - '0', ch = getchar();
    return flag ? -n : n;
}

const int maxn = 20 + 3, maxm = 30 + 3, INF = 0x3f3f3f3f;

struct edge {
    int to, cap, rev;
    edge (int to, int cap, int rev): to(to), cap(cap), rev(rev) {}
};
struct Dinic {
    static const int maxNode = maxn * maxm + 10;
    vector<edge> G[maxNode];
    int iter[maxNode], level[maxNode], s, t;
    void addEdge(int f, int t, int cap) {
        G[f].push_back(edge(t, cap, G[t].size()));
        G[t].push_back(edge(f, 0, G[f].size() - 1));
    }
    bool Bfs() {
        memset(level, -1, sizeof level);
        queue<int> q;
        level[s] = 0, q.push(s);
        while (!q.empty()) {
            int cur = q.front(); q.pop();
            if (cur == t) return true;
            for (int i = 0; i < (int)G[cur].size(); ++i) {
                edge &e = G[cur][i];
                if (e.cap > 0 && level[e.to] == -1) {
                    level[e.to] = level[cur] + 1;
                    q.push(e.to);
                }
            }
        }
        return ~level[t];
    }
    int Dfs(int cur, int flow) {
        if (cur == t || flow == 0) return flow;
        for (int &i = iter[cur]; i < (int)G[cur].size(); ++i) {
            edge &e = G[cur][i];
            if (e.cap > 0 && level[e.to] == level[cur] + 1) {
                int d = Dfs(e.to, min(flow, e.cap));
                if (d > 0) {
                    e.cap -= d;
                    G[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }
    int maxFlow(int s, int t) {
        this -> s = s, this -> t = t;
        int flow = 0, d = 0;
        while (Bfs()) {
            memset(iter, 0, sizeof iter);
            while (d = Dfs(s, INF), d > 0) flow += d;
        }
        return flow;
    }    
}Dinic;

int n, m;

inline int ID(int i, int j) {
    return i * m + j;
}

vector<int> G[maxn * maxm];
int in[maxn * maxm];
bool vis[maxn * maxm];

int main() {
    n = ReadInt(), m = ReadInt();
    int sum = 0, s = n * m, t = s + 1;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j) {
            int p = ReadInt(), w;
            if (p > 0) 
                sum += p, Dinic.addEdge(s, ID(i, j), p);
            else 
                Dinic.addEdge(ID(i, j), t, -p);
            if (j + 1 < m)  {
                G[ID(i, j + 1)].push_back(ID(i, j));
                in[ID(i, j)]++;
            }
            w = ReadInt();
            for (int k = 0; k < w; ++k) {
                int r = ReadInt(), c = ReadInt();
                G[ID(i, j)].push_back(ID(r, c));
                in[ID(r, c)]++;
            }
        }
    queue<int> q;
    for (int i = 0; i < n * m; ++i)
        if (!in[i]) q.push(i);
    while (!q.empty()) {
        int cur = q.front(); q.pop();
        vis[cur] = true;
        for (int i = 0; i < (int)G[cur].size(); ++i) {
            int v = G[cur][i];
            in[v]--;
            if (!in[v]) q.push(v);
        }
    }
    for (int i = 0; i < n * m; ++i) if (vis[i])
        for (int j = 0; j < (int)G[i].size(); ++j) {
            int v = G[i][j];
            if (vis[v]) Dinic.addEdge(v, i, INF);
        }
    for (int i = 0; i < n * m; ++i)
        if (!vis[i]) Dinic.addEdge(i, t, INF);
    printf("%d\n", sum - Dinic.maxFlow(s, t));
    return 0;
}

BZOJ 2324 - [ZJOI2011]营救皮卡丘主席树

Sengxian's Blog