「做题记录」动态规划选做 — Part 2

· · 算法·理论

Part 2 主要是树 / 图上的最优化 DP 问题,会涉及一些 DP 优化。Part 1。

【未完成】P4757 [CERC2014] Parades

P7600 [APIO2021] 封闭道路

给出一棵 n 个节点的无根树,边带权。对于每个 k=0,1,\cdots,n-1 求出:删去一些边使得每个点的度数 \le k,最小化删去的边权之和。

:::::success[题解] 将问题转化为最大化保留边的边权和。

首先是一个暴力 DP:记 f_{u,k} 为不保留 u 处返祖边时,子树内的答案;g_{u,k} 为保留 u 处返祖边时,子树内的答案。

考虑先将儿子全选 f_{u,k},然后反悔,选出 g_{v,k}+w-f_{u,k} 最大的若干个。f_{u,k} 应该由 u 子树中前 k 大的值转移,g_{u,k} 则由前 k-1 大的值转移。

复杂度 O(n^2 \log n),可以获得 24pts。

我们注意到,度数 \le k 的点不受约束。因此考虑枚举 k 时对度数 >k 的点建立虚树,然后在虚树上 DP。由于每个点只会出现度数次,虚树的大小之和就是 O(n) 的。

沿用 f_u 和 g_u 的状态。当我们位于节点 u 时,其儿子被分为两类:

那么只需要维护前 k 大数的和就能转移。在建虚树时修改权值,对每个节点开一棵权值线段树维护,复杂度 O(n \log n)。

:::::info[代码]

const int N = 1e5 + 5, M = 1e9;
int n, deg[N];
vector<pair<int, int>> e[N];

int dn, fa[N], sz[N], dep[N], son[N], top[N], dfn[N], wei[N];
void dfs1(int u) {
    sz[u] = 1, dfn[u] = ++dn;
    for (auto [v, w] : e[u]) {
        if (v == fa[u]) continue;
        fa[v] = u, wei[v] = w, dep[v] = dep[u] + 1, dfs1(v), sz[u] += sz[v];
        if (sz[v] > sz[son[u]]) son[u] = v;
    }
}
void dfs2(int u, int t) {
    top[u] = t;
    if (son[u]) dfs2(son[u], t);
    for (auto [v, w] : e[u]) if (v != fa[u] && v != son[u]) dfs2(v, v);
}
int lca(int u, int v) {
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        u = fa[top[u]];
    } return dep[u] < dep[v] ? u : v;
}

#define ls lson[rt]
#define rs rson[rt]
int tot, rt[N], lson[N << 6], rson[N << 6], cnt[N << 6];
i64 sum[N << 6]; 
void insert(i64 x, i64 l, i64 r, int& rt) {
    if (!rt) rt = ++tot;
    cnt[rt]++, sum[rt] += x;
    if (l == r) return;
    i64 mid = (l + r) >> 1;
    if (x <= mid) insert(x, l, mid, ls);
    else insert(x, mid + 1, r, rs);
}
void remove(i64 x, i64 l, i64 r, int& rt) {
    if (!rt) rt = ++tot;
    cnt[rt]--, sum[rt] -= x;
    if (l == r) return;
    i64 mid = (l + r) >> 1;
    if (x <= mid) remove(x, l, mid, ls);
    else remove(x, mid + 1, r, rs);
}
i64 ask(int k, i64 l, i64 r, int rt) {
    if (rt == 0 || k <= 0) return 0;
    if (cnt[rt] <= k) return sum[rt];
    if (l == r) return l * k;
    i64 mid = (l + r) >> 1;
    if (cnt[rs] >= k) return ask(k, mid + 1, r, rs);
    return sum[rs] + ask(k - cnt[rs], l, mid, ls);
}

bool keep[N];
vector<int> nd[N], ev[N], dr[N];
i64 f[N], g[N];

void dfs3(int u, int k) {
    f[u] = g[u] = 0;
    i64 sum = 0;
    vector<i64> son;
    for (int v : ev[u]) {
        dfs3(v, k);
        if (fa[v] == u && keep[v]) sum += f[v], son.emplace_back(g[v] + wei[v] - f[v]);
        else sum += f[v];
    }
    if (keep[u]) {
        for (i64 x : son) if (x > 0) insert(x, 1, M, rt[u]);
        f[u] = sum + ask(k, 1, M, rt[u]), g[u] = sum + ask(k - 1, 1, M, rt[u]);
        for (i64 x : son) if (x > 0) remove(x, 1, M, rt[u]);
    } else {
        f[u] = sum, g[u] = 0;
    }
}

vector<i64> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W) {
    n = N; i64 sum = 0;
    for (int i = 0; i < n - 1; i++) {
        int u = U[i] + 1, v = V[i] + 1, w = W[i];
        e[u].emplace_back(v, w), e[v].emplace_back(u, w);
        deg[u]++, deg[v]++, sum += w;
    }
    for (int u = 1; u <= n; u++) {
        for (int i = 0; i < deg[u]; i++) nd[i].emplace_back(u);
        dr[deg[u]].emplace_back(u);
    }
    dfs1(1), dfs2(1, 1);
    vector<i64> ans(n); ans[0] = sum;
    i64 bas = 0;
    fill(keep + 1, keep + n + 1, true);
    for (int k = 1; k < n; k++) {
        for (int u : dr[k]) {
            keep[u] = false;
            for (auto [v, w] : e[u]) {
                if (keep[v]) insert(w, 1, M, rt[v]);
                else bas += w;
            }
        }
        vector<int>& a = nd[k];
        if (a.empty()) {
            ans[k] = sum - bas;
            continue;
        }
        sort(a.begin(), a.end(), [](int u, int v) {return dfn[u] < dfn[v];});
        int len = a.size();
        for (int i = 0; i < len - 1; i++) a.emplace_back(lca(a[i], a[i + 1]));
        sort(a.begin(), a.end(), [](int u, int v) {return dfn[u] < dfn[v];});
        a.erase(unique(a.begin(), a.end()), a.end());
        for (int i = 0; i < (int)a.size() - 1; i++) 
            ev[lca(a[i], a[i + 1])].emplace_back(a[i + 1]);
        dfs3(a[0], k);
        ans[k] = sum - bas - f[a[0]];
        for (int i : a) ev[i].clear();
    }
    return ans;
}

:::::

P13534 [OOI 2023] The way home / 回家的路

给出一张 n 个点 m 条边的有向带权图。你需要从节点 1 出发到达节点 n。你初始持有整数 p,经过边 (u,v,w) 后 p \gets p-w,若 p<0 则禁止移动。点带权 a_i,你可以在节点 i 花费 1 的代价使 p \gets p+a_i。

最小化到达终点的代价并输出,或报告无解。

:::::success[题解] 观察性质起手:对于一条 1 \to n 的路径,每次增加 p 只应该发生在 a_i 的前缀最大值处,且应当加到恰好能达到下一个增加点的状态。

基于此,考虑拆点。用 (u,x) 表示当前位于节点 u,且上一个前缀最大值位于点 x。然后设出 DP 为 f_{u,x},用二元组 (c,p) 表示当前代价为 c 和整数 p 的值。

我们的观察已经说明,c 应当取到最小。在此基础上最大化 p 显然更优。这样我们就找到了 (c,p) 上的严格全序,这个最优化 DP 放到图上就是最短路,因此跑 Dijkstra 即可。

注意复杂度为 O(nm \log n)。原因是 (u,x) 只会扩展 (u,v) \in E 的 v 并产生唯一后继 (v,x')。x 只有 O(n) 种,则所有边至多贡献 O(nm) 次。

:::::info[代码]

const int N = 805;
const i64 inf = 1e18;
int n, m, x, num, a[N];
vector<pair<int, int>> e[N];
struct node {
    i64 cnt, pt;
    node(i64 a = inf, i64 b = 0) : cnt(a), pt(b) {}
    bool operator< (const node& a) const {
        if (cnt != a.cnt) return cnt < a.cnt;
        return pt > a.pt;
    }
    bool operator!= (const node& a) const {
        return cnt != a.cnt || pt != a.pt;
    }
} dis[N][N];
struct info {
    int u, x; node w;
    info(int a, int b, node c) : u(a), x(b), w(c) {}
    bool operator< (const info& a) const {return a.w < w;}
};
priority_queue<info> q;
void dijkstra() {
    dis[1][1] = node(0, x);
    q.emplace(1, 1, node(0, x));
    while (!q.empty()) {
        auto [u, x, d] = q.top(); q.pop();
        if (d != dis[u][x]) continue;
        for (auto [v, w] : e[u]) {
            node d0 = d;
            if (d0.pt < w) {
                i64 h = (w - d0.pt + a[x] - 1) / a[x];
                d0.cnt += h, d0.pt += a[x] * h;
            }
            d0.pt -= w;
            int x0 = a[v] > a[x] ? v : x;
            if (d0 < dis[v][x0]) dis[v][x0] = d0, q.emplace(v, x0, dis[v][x0]);
        } 
    }
}

void _main() {
    cin >> n >> m >> x >> num;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1, u, v, w; i <= m; i++) {
        cin >> u >> v >> w;
        e[u].emplace_back(v, w);
    }
    dijkstra();
    node x = *min_element(dis[n] + 1, dis[n] + n + 1);
    cout << (x.cnt >= inf ? -1 : x.cnt);
}

:::::

P4745 [CERC2017] Gambling Guide

给出一张 n 个点 m 条边的无向图。你需要从起点 1 走到终点 n。当你位于节点 u 时,你可以支付 1 的代价并获得一次前往邻接点 v 的机会,你可以选择放弃机会。你需要使最终到达终点的概率为 1,并最小化期望代价。输出期望值,精度要求 10^{-6}。

:::::success[题解] 记 f_u 为从节点 u 出发到达终点的最小期望代价,d_u 为节点 u 的步数,N(u) 为节点 u 邻接点构成的集合。显然 f_n=0。

当我们位于节点 u 且获得了去往 v 的机会时,需要决策是否接受这个机会。为此,钦定一个非空集合 S \subseteq N(u),当 v \in S 时我们接受,否则不接受。

此时 P(v \in S)=\frac{|S|}{d_u},因此在节点 u 处的期望代价为 \frac{d_u}{|S|}。且获得 S 中任意节点的概率是相同的,因此有

f_u=\frac{d_u}{|S|}+\frac{1}{|S|}\sum_{v \in S} f_v=\frac{d_u+\sum_{v \in S} f_v}{|S|}

从上面的式子可以看出,为了让 f_u 最小,我们应当按 f_v 升序将 v 加入 S 中。只要 v 的加入可以使得 f_u 最小就保留。

这一过程非常类似 Dijkstra。最优化 DP 在有环图上的转移顺序正是最短路。因此给出如下流程:

当 u 出队时,所有小于 f_u 的 f_v 已经用来松弛过 f_u,故 f_u 一定取到了最优。这样就不会存在重复入队答案更优的可能性,故上述算法是正确的。

注意为了防止浮点误差,不能像普通 dij 那样懒惰删除,否则会 70pts。需要显式用一个数组判重。

复杂度 O(m \log n)。

:::::info[代码]

const int N = 3e5 + 5;
const double inf = 1e18;
int n, m, cnt[N], vis[N];
vector<int> e[N];
double f[N], sum[N];
struct node {
    int u; double d;
    node(int x = 0, double y = 0) : u(x), d(y) {}
    bool operator< (const node& a) const {return d > a.d;}
};
priority_queue<node> q;

void _main() {
    cin >> n >> m;
    for (int i = 1, u, v; i <= m; i++) {
        cin >> u >> v;
        e[u].emplace_back(v), e[v].emplace_back(u);
    }
    fill(f + 1, f + n + 1, inf), f[n] = 0;
    q.emplace(n, 0);
    while (!q.empty()) {
        auto [u, d] = q.top(); q.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (int v : e[u]) {
            if (vis[v]) continue;
            double nd = (sum[v] + f[u] + e[v].size()) / (cnt[v] + 1);
            if (nd < f[v]) f[v] = nd, sum[v] += f[u], cnt[v]++, q.emplace(v, f[v]);
        }
    }
    cout << fixed << setprecision(12) << f[1];
}

:::::