跳转至

BZOJ1565 植物大战僵尸

题解

链接戳我

我觉得这题是个不错的网络流题目，应用到了对最大权闭合图的理解。

引用一位dalao对闭合图的解释：

闭合图：定义一个有向图 G = (V , E) 的闭合图，是该有向图的一个点集,且该点集的所有出边都还指向该点 集。即闭合图内的任意点的任意后继也一定在闭合图中。更形式化地说，闭合图是这样的一个点集 V ' \in V ,满足对于 \forall u\in V' 引出的 ，必有 v \in V ' 成立。按照上面的定义,闭合图是允许超过一个连通块的。 在许多实际应用中，给出的有向图常常是一个有向无环图( DAG ),闭合图的性质恰好反映了事件间的必要条件的关系：一个事件的发生,它所需要的所有前提也都要发生。一个常见的例子就是制定大学的选课计划,其中一些课程需要以另一些课程为基础，这就是给出了有向无环图。若给所有课程打分,最大权闭合图对应了获益最大或效率最高的选课计划,解决了这个问题,就可以容易地选出一个最合理的选课计划。

假设选择的植物集合为 S，那么我们的目标（需要最大化的值）就是

但是这样并不好决定最大化哪个权值，考虑转化成可以使用最小割求的：

W=\sum\limits_{v_i>0} v_i - (\sum\limits_{i\notin S,v_i>0} v_i+ \sum\limits_{i\in S, v_i<0}|v_i|)

然后考虑最小化括号中的权值，可以想到将点按照权值正负分成二分图，然后按照保护关系连边，但是这样子并不对，因为图中的保护关系可能成环，环中的任意一个点都是不能够被选择的，那就直接拓扑排序后处理一下就行了。

下面说一下连边方法：

  • 对于权值大于 0 的点 u ，连边 (S, u, v_u)。
  • 对于权值小于 0 的点 u ，连边 (u,T, -v_u) 。
  • 对于两个点 i,j，若 i 保护 j 且i,j 均不在环中，连边 (j, i, inf) ，表示要选 j 就必须选 i。
  • 对于在环上的某个点 u, 连边 (u, T, inf) 表示绝对不会选。

这就是最大权闭合图建图的套路，正确性的证明参见胡伯涛的论文

最后的答案就是所有正权值的和减去最小割。

程序

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
#include <vector>
#define INF 1e9
#define MAX_N 2007
#define MAX_M 1000007

int N, M, S, T;
int idx[37][37], sz, val[37][37];
int head[MAX_N], to[MAX_M], nxt[MAX_M], cap[MAX_M], cur[MAX_N], tot = 1;
int flow, sum, deg[MAX_N], dep[MAX_N];
bool vis[MAX_N];
std::vector<int> prot[MAX_N];
std::queue<int> q;

void addEdge (int u, int v, int c) {
    nxt[++tot] = head[u];
    head[u] = tot;
    to[tot] = v;
    cap[tot] = c;
}

void add (int u, int v, int c) {
    addEdge(u, v, c);
    addEdge(v, u, 0);
}

void topSort () {
    for (int i = 1;i <= sz; ++i) {
        if (!deg[i]) {
            vis[i] = true;
            q.push(i);
        }
    }
    while (!q.empty()) {
        int x = q.front(); q.pop();
        for (int m = prot[x].size(), i = 0;i < m; ++i) {
            deg[prot[x][i]]--;
            if (!deg[prot[x][i]]) 
                q.push(prot[x][i]), vis[prot[x][i]] = true;
        }
    }
}

void make () {
    for (int i = 1;i <= N; ++i) {
        for (int j = 1;j <= M; ++j) {
            if (val[i][j] >= 0) 
                add(S, idx[i][j], val[i][j]);
            else
                add(idx[i][j], T, -val[i][j]);
        }
    }
    for (int i = 1;i <= sz; ++i) {
        if (vis[i]) {
            for (int m = prot[i].size(), j = 0;j < m; ++j) {
                if (vis[prot[i][j]]) 
                    add(prot[i][j], i, INF);
            }
        } else {
            add(i, T, INF);
        }
    }
}

inline bool bfs () {
    memset(dep, -1, sizeof(dep));
    for (int i = 1;i <= T; ++i)
        cur[i] = head[i];
    dep[S] = 0;
    q.push(S);
    while (!q.empty()) {
        int x = q.front(); q.pop();
        for (int i = head[x]; i; i = nxt[i]) {
            if (cap[i] && dep[to[i]] == -1) {
                dep[to[i]] = dep[x] + 1;
                q.push(to[i]);
            }
        }
    }
    return dep[T] != -1;
}

int dfs (int x, int a) {
    if (x == T || a == 0) return a;
    int fl = 0, f;
    for (int& i = cur[x]; i; i = nxt[i]) {
        if (cap[i] && dep[to[i]] == dep[x] + 1) {
            f = dfs(to[i], std::min(cap[i], a - fl));
            cap[i] -= f;
            cap[i ^ 1] += f;
            fl += f;
            if (fl == a) return fl;
        }
    }
    return fl;
}

void dinic () {
    while (bfs())
        flow += dfs(S, INF);
}

int main () {
    scanf("%d%d", &N, &M);
    for (int i = 1;i <= N; ++i) 
        for (int j = 1;j <= M; ++j)
            idx[i][j] = ++sz;
    S = ++sz, T = ++sz;
    sz -= 2;
    int x, y, z;
    for (int i = 1;i <= N; ++i) {
        for (int j = 1;j <= M; ++j) {
            scanf("%d%d", val[i] + j, &z);
            sum += (val[i][j] > 0 ? val[i][j] : 0);
            for (int k = 1;k <= z; ++k) {
                scanf("%d%d", &x, &y);
                x++, y++;
                deg[idx[x][y]]++;
                prot[idx[i][j]].push_back(idx[x][y]);
            }
            if (j > 1) {
                deg[idx[i][j - 1]]++;
                prot[idx[i][j]].push_back(idx[i][j - 1]);
            }
        }
    }
    topSort();
    make();
    dinic();
    printf("%d\n", sum - flow);
    return 0;
}