Codeforces 1955H 最小费用流 / DP

题意

传送门 Codeforces 1955H The Most Reckless Defense

题解

不同塔对敌人的贡献是独立的。考虑任一座塔，赋予其 $r$ 的攻击范围，则其对敌人的造成伤害的上界为 $nmp<3^{lg},lg=13$ ，则当 $r\geq lg$ ，则塔对敌人造成的伤害与初始化增加的生命值两者的总贡献为正，此时显然取 $r = 0$ 更优。故只需考虑 $r < l g$ 的情况。分别以塔和 $r$ 为左右节点构造带权二分图，问题转化为求匹配数任意情况下的最小权匹配。构造邻接矩阵的时间复杂度为 $O(lg^{3}\times k)$ 。

最小费用流

新增源点、汇点，将带权二分图建模为网络流，构造势函数保证边权非负，使用dijkstra算法不断增广。图中带负权边，为了构造势函数，可以初始化时使用Bellman-Ford算法；而此处的图具备良好的性质，即每次增广所用的边数 $k$ 都是相等的（不妨假设增广路中每条反向边可以抵消一条原边），即 $k = 1$ ，此时只需为每条边加上一个 $d$ 转化为非负权值，每次求增广路时减去 $k\times d$ 即可还原得到原始路径权值。

那么对于流量任意的最小费用流，只需在残余网络存在权值为负的路径情况下不断增广。令二分图左部点数量为 $n = l g$ ，右部点数量为 $m = k$ ，则总时间复杂度 $O\big(n^2m\log(n + m)\big)$ 。

tourist的这份提交似乎实现了一种不需要保证完备匹配的Hungarian算法，其复杂似乎是 $O(n^2m)$ 。

#include <bits/stdc++.h>
using namespace std;
constexpr int INF = 1e9;
struct MinimumCostFlow {
    struct Edge {
        int to, cost, cap, rev;
    };
    vector<vector<Edge>> g;
    vector<int> h, used, ds;
    vector<int> prevv, preve;
    int delta;

    MinimumCostFlow(int n, int d) : g(n), h(n), used(n), ds(n), prevv(n), preve(n), delta(d) {
    }

    void add_edge(int from, int to, int cost, int cap) {
        g[from].push_back({to, cost, cap, (int)g[to].size()});
        g[to].push_back({from, -cost, 0, (int)g[from].size() - 1});
    }

    pair<int, int> min_cost_flow(int s, int t) {
        fill(h.begin(), h.end(), 0);
        int flow = 0, res = 0;
        for (;;) {
            fill(used.begin(), used.end(), 0);
            fill(ds.begin(), ds.end(), INF);
            using P = pair<int, int>;
            ds[s] = 0;
            priority_queue<P, vector<P>, greater<P>> q;
            q.push({ds[s], s});
            while (!q.empty()) {
                int v = q.top().second;
                q.pop();
                if (used[v]) {
                    continue;
                }
                used[v] = 1;
                for (int i = 0; i < (int)g[v].size(); ++i) {
                    auto [to, cost, cap, _] = g[v][i];
                    if (cap > 0) {
                        if (ds[to] > ds[v] + cost + h[v] - h[to]) {
                            ds[to] = ds[v] + cost + h[v] - h[to];
                            prevv[to] = v;
                            preve[to] = i;
                            q.push({ds[to], to});
                        }
                    }
                }
            }
            if (ds[t] == INF) {
                break;
            }
            for (int v = 0; v < (int)g.size(); ++v) {
                if (ds[v] != INF) {
                    h[v] += ds[v];
                }
            }
            if (h[t] - delta >= 0) {
                break;
            }
            int d = INF;
            for (int v = t; v != s; v = prevv[v]) {
                auto &e = g[prevv[v]][preve[v]];
                d = min(d, e.cap);
            }
            flow += d;
            res += d * h[t];
            for (int v = t; v != s; v = prevv[v]) {
                auto &e = g[prevv[v]][preve[v]];
                e.cap -= d;
                g[e.to][e.rev].cap += d;
            }
        }
        return {flow, res};
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int tt;
    cin >> tt;
    while (tt--) {
        int n, m, k;
        cin >> n >> m >> k;
        vector<string> mat(n);
        for (int i = 0; i < n; ++i) {
            cin >> mat[i];
        }
        vector<array<int, 3>> towers(k);
        for (int i = 0; i < k; ++i) {
            auto &[x, y, p] = towers[i];
            cin >> x >> y >> p;
            x -= 1, y -= 1;
        }
        const int mx_lg = 12;
        vector<vector<int>> cost(k, vector<int>(mx_lg));
        auto judge = [&](int x, int y) {
            return 0 <= x && x < n && 0 <= y && y < m;
        };
        int p3 = 1;
        for (int r = 1; r <= mx_lg; ++r) {
            p3 *= 3;
            for (int i = 0; i < k; ++i) {
                int sum = 0;
                auto [x, y, p] = towers[i];
                for (int dx = -r; dx <= r; ++dx) {
                    for (int dy = -r; dy <= r; ++dy) {
                        int nx = x + dx, ny = y + dy;
                        if (judge(nx, ny) && dx * dx + dy * dy <= r * r && mat[nx][ny] == '#') {
                            sum += p;
                        }
                    }
                }
                cost[i][r - 1] = p3 - sum;
            }
        }

        auto matching = [&]() {
            int s = mx_lg + k, t = s + 1;
            int n = t + 1;
            const int delta = 2e6;
            MinimumCostFlow mcf(n, delta);
            for (int i = 0; i < mx_lg; ++i) {
                mcf.add_edge(s, i, 0, 1);
            }
            for (int i = 0; i < k; ++i) {
                mcf.add_edge(mx_lg + i, t, 0, 1);
            }
            for (int i = 0; i < k; ++i) {
                auto &c = cost[i];
                for (int j = 0; j < (int)c.size(); ++j) {
                    if (c[j] >= 0) {
                        continue;
                    }
                    mcf.add_edge(j, mx_lg + i, delta + c[j], 1);
                }
            }
            auto [flow, res] = mcf.min_cost_flow(s, t);
            res -= flow * delta;
            return res * -1;
        };
        cout << matching() << '\n';
    }

    return 0;
}

DP

由于 $l g$ 非常小，可以使用状态压缩DP更加方便地求解上述最小权匹配问题。总时间复杂度 $O(k\times lg2^{lg})$ 。

#include <bits/stdc++.h>
using namespace std;
constexpr int INF = 1e9;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int tt;
    cin >> tt;
    while (tt--) {
        int n, m, k;
        cin >> n >> m >> k;
        vector<string> mat(n);
        for (int i = 0; i < n; ++i) {
            cin >> mat[i];
        }
        vector<array<int, 3>> towers(k);
        for (int i = 0; i < k; ++i) {
            auto &[x, y, p] = towers[i];
            cin >> x >> y >> p;
            x -= 1, y -= 1;
        }
        const int mx_lg = 12;
        vector<vector<int>> cost(k, vector<int>(mx_lg));
        auto judge = [&](int x, int y) {
            return 0 <= x && x < n && 0 <= y && y < m;
        };
        int p3 = 1;
        for (int r = 1; r <= mx_lg; ++r) {
            p3 *= 3;
            for (int i = 0; i < k; ++i) {
                int sum = 0;
                auto [x, y, p] = towers[i];
                for (int dx = -r; dx <= r; ++dx) {
                    for (int dy = -r; dy <= r; ++dy) {
                        int nx = x + dx, ny = y + dy;
                        if (judge(nx, ny) && dx * dx + dy * dy <= r * r && mat[nx][ny] == '#') {
                            sum += p;
                        }
                    }
                }
                cost[i][r - 1] = p3 - sum;
            }
        }
        auto _min = [&](int &x, int y) {
            x = min(x, y);
        };
        vector<int> dp(1 << mx_lg, INF);
        dp[0] = 0;
        for (int i = 0; i < k; ++i) {
            for (int j = (1 << mx_lg) - 1; j >= 0; --j) {
                for (int l = 0; l < mx_lg; ++l) {
                    if (~j >> l & 1) {
                        _min(dp[j | 1 << l], dp[j] + cost[i][l]);
                    }
                }
            }
        }
        int res = 0;
        for (int i = 0; i < 1 << mx_lg; ++i) {
            res = min(res, dp[i]);
        }
        res *= -1;
        cout << res << '\n';
    }

    return 0;
}