BZOJ 1104 - [POI2007]洪水pow

#贪心 #数据结构 #并查集

Published on 2016-09-13

描述

　AKD 市处在一个四面环山的谷地里。最近一场大暴雨引发了洪水，AKD 市全被水淹没了。Blue Mary，AKD 市的市长，召集了他的所有顾问（包括你）参加一个紧急会议。经过细致的商议之后，会议决定，调集若干巨型抽水机，将它们放在某些被水淹的区域，而后抽干洪水。你手头有一张 AKD 市的地图。这张地图是边长为 $m\times n$ 的矩形，被划分为 $m\times n$ 个 $1\times 1$ 的小正方形。对于每个小正方形，地图上已经标注了它的海拔高度以及它是否是 AKD 市的一个组成部分。地图上的所有部分都被水淹没了。并且，由于这张地图描绘的地面周围都被高山所环绕，洪水不可能自动向外排出。显然，我们没有必要抽干那些非 AKD 市的区域。每个巨型抽水机可以被放在任何一个 $1\times 1$ 正方形上。这些巨型抽水机将持续地抽水直到这个正方形区域里的水被彻底抽干为止。当然，由连通器原理，所有能向这个格子溢水的格子要么被抽干，要么水位被降低。每个格子能够向相邻的格子溢水，“相邻的”是指（在同一高度水平面上的射影）有公共边。

分析

这题卡了我半天，我必须证明它！

首先，根据题意，水可以从海拔高的地方向海拔低的地方流，这就推出：

引理一：如果 $A$ 处有抽水机，且 $A\rightarrow B$ 的某条路径上没有海拔大于 $B$ 的点，则 $B$ 被抽干。
证明：显然，不管你 $A\rightarrow B$ 上的路径怎样起伏，我 $B$ 点不比它们低，所以 $A$ 抽水一定会将 $B$ 抽干。我们称这种路径为 $A\rightarrow B$ 的合法路径。

我们先定义一个“块”的概念：假如 $A$ 有抽水机，那么 $A$ 所在的块是所有可以被 $A$ 抽干的格子到 $A$ 的合法路径上的点形成的点集。
引理二：存在某个最优答案，使得所有抽水机一定放在某个块的海拔的极小处。
证明：假设 $A$ 最小，那么 $A$ 的块中别的地方放抽水机，答案不更小。

引理三：存在某个最优答案，使得所有抽水机都放在城市上。
证明：假设有一个抽水机放在了 $A$ 上， $A$ 不是城市。如果 $A$ 所在的块没有城市，那么 $A$ 可以不放抽水机，与最优答案矛盾。
如果 $A$ 所在的块有城市，那么我们将抽水机从 $A$ 换到最小海拔城市 $B$ 上，不影响答案，为什么呢？根据引理二， $A$ 的海拔不大于 $B$ 的海拔，如果有城市 $C$ 是通过路径 $A\rightarrow C$ 来实现抽干的，那么 $B \rightarrow A \rightarrow C$ 同样能实现抽干，因为 $B\rightarrow A$ 的最高海拔 $\le B$ ，而 $B$ 又是城市中海拔最小的，所以 $B\rightarrow C$ 的路径最高海拔仍然 $\le C$ 。那 $A$ 没被抽干怎么办呢？别忘了 $A$ 不是城市无需抽干。

据此可以得出一个算法的过程：从小到大枚举高度 $h$ ，对于所有高度为 $h$ 的点 $x$ ，将它与它四周相邻的高度不超过 $h$ 的点所在的集合合并。做完所有 $h$ 高度的合并以后，对于所有高度为 $h$ 的城市 $x$ ，如果它所在集合没有放置任何点放置了水泵，则在此城市放置一个水泵。

定理（洪水定理）：上述算法能够得出最优答案。
证明：我们得出的答案是 $k$ ，假设存在一个 $k - 1$ 的答案，那么必然存在一个点 $A$ ，它在我们得出答案中放置了水泵而在 $k - 1$ 的答案中没有放置水泵，这说明在 $k - 1$ 的答案中，必然存在一个点 $B$ ，它的海拔小于等于 $A$ ，而且存在一条 $B\rightarrow A$ 的合法路径。但是这条路径不可能存在，如果存在，那么我们的算法在从小到大加边的过程中，必然会使得 $A, B$ 在一个并查集，既然 $B$ 已经满足被抽干，那么 $A$ 无需再放抽水机（这就要求我们处理相等的高度的时候，先做完合并，再来放抽水机，否则这一步不成立！），而现在 $A$ 处放了抽水机，说明 $A, B$ 不在一个并查集，也就没有这样一条路径，证明完毕！

证明可能漏洞百出，有问题直接在底下留言，感激不尽。

代码

//  Created by Sengxian on 9/12/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 1104 并查集 + 贪心
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
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 << 3) + (n << 1) + ch - '0', ch = getchar();
    return flag ? -n : n;
}

const int MAX_N = 1000 + 3, MAX_M = 1000 + 3, MAX_V = 1000 + 3;
int n, m, cnt = 0, a[MAX_N][MAX_M];

bool vis[MAX_N][MAX_M];

struct Point {
    int x, y;
    Point(int x = 0, int y = 0): x(x), y(y) {}
} ps[MAX_N * MAX_M];

const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};

namespace union_set {
    int fa[MAX_N * MAX_M];
    bool v[MAX_N * MAX_M];
    inline void init(int n) {
        for (int i = 0; i < n; ++i) fa[i] = i, v[i] = false;
    }
    inline int find(int x) {
        return fa[x] == x ? x : fa[x] = find(fa[x]);
    }
    inline void unite(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return;
        fa[x] = y, v[y] |= v[x];
    }
}

using namespace union_set;

vector<Point> G[MAX_V];
bool type[MAX_N][MAX_M];

#define ID(i) (i.x * m + i.y)

int main() {
    n = ReadInt(), m = ReadInt();
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j) {
            a[i][j] = ReadInt();
            if (a[i][j] >= 0) type[i][j] = true;
            else a[i][j] = -a[i][j];
            G[a[i][j]].push_back(Point(i, j));
        }

    init(n * m);
    int ans = 0;
    for (int i = 0; i < MAX_V; ++i) {
        for (int j = 0; j < (int)G[i].size(); ++j) {
            Point now = G[i][j];
            for (int k = 0; k < 4; ++k) {
                Point ne = Point(now.x + dx[k], now.y + dy[k]);
                if (ne.x >= 0 && ne.y >= 0 && ne.x < n && ne.y < m) {
                    if (a[now.x][now.y] < a[ne.x][ne.y]) continue;
                    unite(ID(now), ID(ne));
                }
            }
        }
        for (int j = 0; j < (int)G[i].size(); ++j) {
            Point now = G[i][j];
            if (type[now.x][now.y]) {
                int x = find(ID(now));
                if (!v[x]) v[x] = true, ans++;
            }
        }
    }

    printf("%d\n", ans);
    return 0;
}

BZOJ 1107 - [POI2007]驾驶考试egz BZOJ 1086 - [SCOI2005]王室联邦

Sengxian's Blog

BZOJ 1104 - [POI2007]洪水pow

描述

分析

代码