「做题记录」动态规划选做 — Part 2
stripe_python · · 算法·理论
Part 2 主要是树 / 图上的最优化 DP 问题,会涉及一些 DP 优化。Part 1。
【未完成】P4757 [CERC2014] Parades
P7600 [APIO2021] 封闭道路
给出一棵
n 个节点的无根树,边带权。对于每个k=0,1,\cdots,n-1 求出:删去一些边使得每个点的度数\le k ,最小化删去的边权之和。
:::::success[题解] 将问题转化为最大化保留边的边权和。
首先是一个暴力 DP:记
考虑先将儿子全选
复杂度
我们注意到,度数
沿用
- 虚树外的点:权值为
w ; - 虚树内的点:权值为
g_v+w-f_v 。
| 那么只需要维护前 |
|---|
:::::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[题解]
观察性质起手:对于一条
基于此,考虑拆点。用
我们的观察已经说明,
| 注意复杂度为 |
|---|
:::::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[题解]
记
当我们位于节点
此时
从上面的式子可以看出,为了让
这一过程非常类似 Dijkstra。最优化 DP 在有环图上的转移顺序正是最短路。因此给出如下流程:
- 用一个优先队列维护
(u,f_u) 二元组,初始加入(n,0) ; - 每次取出堆顶节点
u ,用f_u 去更新f_v ; - 对于节点
v ,尝试将u 加入集合S ,若这一操作使得f_v 更小,则保留并将(v,f_v) 入堆。
当
注意为了防止浮点误差,不能像普通 dij 那样懒惰删除,否则会 70pts。需要显式用一个数组判重。
| 复杂度 |
|---|
:::::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];
}
:::::