BZOJ1565 植物大战僵尸

文章目录

题解

题目链接

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

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

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

假设选择的植物集合为 $S$,那么我们的目标(需要最大化的值)就是

$$ W=\sum\limits_{i\in S} v_i=\sum\limits_{i\in S, v_i>0} v_i – \sum\limits_{i\in S, v_i <0} |v_i| $$

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

$$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)$ 表示绝对不会选。

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

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

程序

#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;
}

sys_con

OIer,常规 / 竞赛都渣得不行

发表评论

电子邮件地址不会被公开。 必填项已用*标注