SSL-OI夏日合宿 杂题 POI2018水箱 最小生成树

摘要： 文章讨论了POI2018中的水箱问题（luoguP5952），该问题要求计算一个$n*m$方格水箱中，水位高度不超过$H$的情况下，有多少种不同的水位分布。文章提出了一种基于最小生成树的解决方案，通过从小到大枚举墙的高度，合并水域并计算答案。算法使用并查集来维护水域的合并，并通过优先队列来处理墙的合并顺序。最终，程序输出水位分布的总数，该数对$10^9+7$取模。文章还提到了一些实现细节，如数组大小和优化技巧。

POI2018

luoguP5952

题意

给一个$n*m$的方格水箱, 相邻两个格子之间有一道有高度的墙.

墙的高度和水位不超过$H$, 问: 有多少种水位情况.

两种情况不同当且仅当存在至少一个格子在两种情况中的水位高度不同(高度是整数).

故事

今天故事即正解, 走向人生巅峰.

不知道为啥这题好眼熟, 总感觉是刚学OI那会$_{儿}$试图去做但没做出来的题目.

显然如果我们从小往大枚举水位, 每个格子只会被最低一个墙影响(合并). 那么就从小往大枚举墙, 合并两个水域的时候尝试合并两个答案.

设$f_i$是水域$i$的答案, $g_i$是水域$i$的高度. 刚开始每个格子都是一个水域, 且高度为$0$. 若将水域$i$和水域$j$合并成水域$k$, 且合并的墙高为$h$, 转移为:

$$ f_k=(f_i+h-g_i)*(f_j+h-g_j)\\ g_k=h. $$

(一个格子$i$从水位$g_i$提升到$h$有$h-g_i$种水位)

总结: 我们发现这是一个最小生成树的过程, 那么直接建图跑最小生成树, 合并的时候统计答案就好. (我当初怎么没想到)

在这种记点方式下注意数组大小

写丑了一点吸氧过的

#define MXNM (5000020)
#define XJQ (1000000007)

#include <stdio.h>

#include <queue>

int n, m, H;

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

struct Edge {
    int u, v, w;
    bool operator<(const Edge E) const { return w > E.w; }
};

long long f[MXNM], g[MXNM];

std::priority_queue<Edge> edge;

int fa[MXNM];

int find(int x) { return (fa[x] == x) ? (x) : (fa[x] = find(fa[x])); }
void merge(int x, int y, long long h) { x = find(x), y = find(y), f[x] = ((f[x] + h - g[x]) * (f[y] + h - g[y])) % XJQ, g[x] = h, fa[y] = x; }

signed main() {
#ifndef ONLINE_JUDGE
    freopen("P5952.in", "r", stdin);
#endif

    scanf("%d%d%d", &n, &m, &H);

    for (int i = 1, j, w; i <= n; ++i)
        for (j = 1; j < m; ++j)
            scanf("%d", &w), edge.push(Edge{node(i, j), node(i, j + 1), w});
    for (int i = 1, j, w; i < n; ++i)
        for (j = 1; j <= m; ++j)
            scanf("%d", &w), edge.push(Edge{node(i, j), node(i + 1, j), w});
    for (int i = 1, j; i <= n; ++i)
        for (j = 1; j <= m; ++j)
            fa[node(i, j)] = node(i, j), f[node(i, j)] = 1;

    for (int i = n * m; i > 1; --i) {
        while ((!edge.empty()) && (find(edge.top().u) == find(edge.top().v))) edge.pop();
        if (!edge.empty()) merge(edge.top().u, edge.top().v, edge.top().w);
    }

    printf("%lld", (f[find(node(1, 1))] + H - g[find(node(1, 1))]) % XJQ);

    return 0;
}

反正就是一道小水题, 不知道怎么变成紫题的, 不知道怎么被北大爷选进杂题的.