算法小站
首页
wiki
新鲜事
文章搜索
网站导航
回忆录
首页
wiki
新鲜事
文章搜索
网站导航
回忆录
登录
注册
算法基础
搜索
数据结构
字符串
数学
图论
动态规划
计算几何
杂项
图的dp
DAG上的dp(按拓扑序dp),一般图迭代(最短路思想),图 .....
[[ slider_text ]]
[[ item.c ]]
0
0
图的dp
发布时间
2024-10-05
作者:
zhangminchen
来源:
算法小站
期望dp
图dp
## Codeforces Round 261 (Div. 2) **[Codeforces Round 261 (Div. 2) E. Pashmak and Graph](https://codeforces.com/contest/459/problem/E)** **问题描述** 带边权的有向图,要找一条路径(不要求是简单路径,路径可以经过同一个点) 要求边权是递增的,另外经过的边数要尽量多 ### 算法分析 要求边权递增,可以考虑按边权的大小进行 dp,不难写出转移方程 $$dp(u, v) = \max_w( dp(w, u) + 1 ) \ (w, u) < (u, v) $$,直接做是$$O(n^2)$$的 可以考虑按边权排序,将每一条边$$(u, v, w)$$,**挂载到权值数组中**,这样 dp 到 $$w$$ 的时候, 实际上我们只考虑了$$< w$$的边,这个时候记 $$dp(u)$$,表示经过这些$$< w$$的边走到$$u$$, 可以走的最多的边数,那么我们有$$dp(v) = \max (dp(u) + 1)$$ 现在还有一个问题,边权相等的时候怎么办? 可以对每一个`(u, v)`,用`tmp[v]`把`dp[u] + 1`的值先存起来,然后更新`max( dp(v), tmp(v), dp(u) + 1 )` 对同一个权值的,要缓存一下,然后同时更新,取最大值,这样就可以处理权值相同的情况了 ### 算法实现 ```bash int main() { for (int i = 0; i < m; i++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); e[w].push_back({u, v}); } for (int w = 1; w <= 1e5; w++) { for (auto [u, v] : e[w]) { tmp[v] = max({tmp[v], dp[v], dp[u]+1}); } for (auto [u, v] : e[w]) dp[v] = tmp[v]; } auto ans = *max_element(dp.begin(), dp.end()); } ``` ## Codeforces Round 374 (Div. 2) **[Codeforces Round 374 (Div. 2) C. Journey](https://codeforces.com/contest/721/problem/C)** **问题描述** 给定一个 dag,每条边有边权,从$$1$$走到$$n$$,找到一条路径,使得边权总和$$\leqslant T$$ 使得路径上经过的点尽量多 ### 算法分析 类似背包,定义$$dp(i, T)$$表示在$$i$$这个点,还剩下$$T$$的边权可以走,走到$$n$$最多经过的点 那么存在转移,对于边$$j \to i$$,有$$dp(i, T) = \max_j \\{ dp(j, T-w(i, j)) + 1 \\}$$ 注意到$$T$$范围很大,但是$$dp(i, T)$$的范围很小 定义$$dp(i, j)$$,表示从$$i$$开始,还有$$j$$步可走(走了至少$$j$$步),走到$$n$$,所需要的最短时间 最后答案就是求满足$$dp(1, k) \leqslant T$$的最大的$$k$$ 对于边$$(u \to v), \quad dp(u, j) = \min \\{ dp(v, j-1) + 1 \\}$$ 可以把$$j$$这一维作为 dp 的阶段,这样能少写一个拓扑排序 ### 算法实现 ```bash int main() { vector<vector<int> > dp(maxn, vector<int>(maxn, inf)), nxt(maxn, vector<int>(maxn, 0)); dp[n][0] = 0; for (int j = 1; j <= n; j++) { for (int i = 0; i < m; i++) { auto [u, v, w] = e[i]; if (chmin( dp[u][j], dp[v][j-1] + w )) { nxt[u][j] = v; } } } int ans = 1; for (int j = 1; j <= n; j++) if (dp[1][j] <= T) ans = j; printf("%d\n", ans + 1); vector<int> path; int u = 1, t = ans; while (u != n) { path.push_back(u), u = nxt[u][t]; t--; } for (auto u : path) printf("%d ", u); } ``` ## NOIP 提高组2017 **[NOIP2017 提高组 逛公园](https://www.luogu.com.cn/problem/P3953)** **问题描述** 给定一个有向图,没有重边和自环,边权非负,起点是$$1$$终点是$$n$$,从$$1 \to n$$ 假设最短路的长度是$$d$$,问有多少条长度不超过$$d+K$$的路线,注意这里$$K$$很小,只有$$\leqslant 50$$ ### 算法分析 首先考虑一些简单情况,假设边数很小,并且没有$$0$$的边,可以记 $$dp(u, j)$$表示从$$1 \to u$$,路径的总长度为$$j$$,此时的方案数 那么对于边$$u\to v$$,可以转移到$$dp(v, j + w(u, v))$$,但这样做显然复杂度太大了 注意到$$K$$很小,考虑$$dis(u)$$表示从$$1 \to u$$所经过的**最短路径**的长度,那么$$j \geqslant dis(u)$$是成立的 另外我们要求长度不超过$$dis(u) + K$$,也就是说$$j \leqslant dis(u) + K$$ 考虑重新设计状态 $$dp(u, j)$$表示从$$1 \to u$$,经过的路径长度是$$dis(u)+j$$的方案数 也就是说,把**比最短路多走了多少**,这个$$\Delta$$作为第二维,来进行 dp 那么$$j$$沿着$$u \to v$$能走到哪里呢?注意这里的$$j$$是指比最短路多走的$$\Delta$$ $$j \to j + dis(u) + w(u, v) - dis(v)$$ 这样就可以建一张新图,在原来图中跑完最短路之后,把边权改成$$dis(u) + w(u, v) - dis(v)$$ 而根据最短路边的 relax 操作,我们一定有$$dis(u) + w(u, v) \geqslant dis(v)$$ 所以新图的边权仍然是非负的,这样原问题就转换成如下问题 > 在新的图从$$1 \to n$$,距离$$\leqslant K$$的路径总数(方案数) 考虑**拆点**,一个点拆成$$K+1$$个点,表示到达$$u$$这个点,距离分别是$$[0\cdots K]$$ 在新图上,$$(1, 0) \to (n, ?)$$,有多少条路径? 解决几个问题 第一,路径是否无限多条,第二,不是无限多的话,有多少条? 如果存在环,并且在环上绕了之后能够走到$$(n, ?)$$,那么路径就有无限多条。具体来说 要找到所有$$(1, 0)$$可达的点,并且这些点都能到$$(n, ?)$$,判断这些点是不是 dag 如果不是 dag,那么就存在环,有无限多这样的路径 如果是 dag,考虑拓扑序 dp > 简单一点可以 dfs 判环,节点初始状态设置为白色,dfs-visit 节点的时候,节点染成灰色 dfs-visit 完成的时候,节点染成灰色,如果 dfs-visit 访问的过程中出现了灰色节点,那么就有环 ```bash dfs(G): for u = 1 to n: if color(u) == WHITE: dfs-visit(u) dfs-visit(u): u.color = GRAY for v in G(u): if color(v) == GRAY: return 存在环 if color(v) == WHITE: return dfs-visit(v) u.color = BLACK return 没有环 ``` 具体实现 dp 的过程,可以用记忆化搜索 * 预处理,先在反图上跑一遍`dijkstra`,$$d(u)$$表示从$$u$$这个点到终点还有多少步可以走 * $$dp(u, c)$$表示,拆点之后,$$u$$这个位置到终点,还有$$c$$的距离可以走,此时的方案数 我们有 $$dp(u, c) = \sum_v dp(v, c+d_u - w(u, v) - d_v)$$ * 一边 dfs 记忆化搜索的时候,一边判环,访问$$(u, c)$$的时候,将其标记为在栈中 `ins(u, c) = 1`,访问完的时候记一下`ins(u, c) = 0` 如果 dfs 到了一个`ins(u, ?) = 1`的点,那么就说明遇到环了 ### 算法实现 ```bash void solve() { scanf("%d%d%d%d", &n, &m, &K, &P); vector<vector<PII> > G(n+1), Grev(n+1); for (int i = 0; i < m; i++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); G[u].push_back({v, w}), Grev[v].push_back({u, w}); } vector<int> d(maxn, inf); dijkstra(n, d, Grev); vector<vector<int> > f(n+1, vector<int>(K+5, 0)), ins(n+1, vector<int>(K+5, 0)); function<int(int, int)> dp = [&](int u, int c) -> int { if (c < 0 || c > K) return 0; int &ans = f[u][c]; if (ans) return ans; if (ins[u][c]) return -1; if (u == n) ans += 1; ins[u][c] = 1; for (auto [v, w] : G[u]) { auto cost = dp(v, c+d[u]-w-d[v]); if (cost == -1) return -1; ans = (ans + cost) % P; } ins[u][c] = 0; return ans; }; auto ans = dp(1, K); if (ans == -1) puts("-1"); else printf("%d\n", ans); } ``` ## Codeforces Round 335 (Div. 1) **[Codeforces Round 335 (Div. 1) E. Intergalaxy Trips](https://codeforces.com/problemset/problem/605/E)** **问题描述** 需要从$$1$$号点走到$$n$$号点,$$(i, j)$$有一条边,它每天以$$p(i, j)$$的概率出现 每一天有$$2$$种决策,一种决策是,当一条边出现的时候,就走过去 还有一种决策是你等一天,问走到$$n$$号点期望要多少天 换句话说,如果$$1\to 2$$这条边已经出现了,那么直接走过去 如果没有出现,那么需要罚站一天,直到等到这条边出现再过去,如果$$p(1, 2) = 0.8$$ 那么从$$1 \to 2$$的时间期望是$$1 /0.8 = 1.25$$天 以样例为说明,$$(1, 3)$$直达终点的边,第一天出现的概率是$$0.5$$ 那么有$$0.5$$的概率,只需要花一天直达终点 同时有$$0.5$$的概率不出现,我们已经算出来$$2 \to 3$$的期望天数是$$1/0.8 = 1.25$$天 那么走$$1 \to 2$$这条边有$$0.5 \times 0.5 = 0.25$$的概率出现 因此有$$0.25$$的概率需要$$1 + 1.25 = 2.25$$天 可以列出期望方程$$E = 0.5 \times 1 + 0.25 \times 2.25 + 0.25 \times (E + 1)$$ 求解期望即可 ### 算法分析 不妨设对于每个点$$u$$,它到终点的期望步数是$$E_u$$,考虑如何决策 可以对$$u$$的每一条出边,相应的按$$E_i$$从小到大排序,如果我们发现一条边走到的点$$k$$ $$E_u < E_k$$,我们是不会走的,而是选择等一天 特别地,我们可以令$$E_n = 1$$,我们有方程 ```math E_u = p_1 \cdot E_{v1} + (1-p_1)\cdot p_2 \cdot E_{v2} + \cdots + (1-p_1)(1-p_2)\cdots (1-p_{k-1})\cdot p_k \cdot E_{vk} \\ +(1-p_1)\cdots (1-p_k)(1+E_u) ``` 注意到可以利用最短路思想来解决 一开始所有点的期望都设成$$\infty$$,$$E_n = 0$$,然后我们每一步都选$$E$$最小的那个点 比如我们要确定$$E_1$$ 一开始我们假设其他边都没有出现 $$E\_1 = 1 + p\_{1, n} \cdot E\_n + (1-p\_{1, n}) \cdot E_1$$ 当我们挨个确定出$$E\_i$$的时候,调整$$E\_1$$的值如下 ```math E_1 = 1 + p_{1, n} E_n + (1-p_{1, n})p_{1, n-1}E_{n-1} + \cdots + \\ (1-p_{1, n})(1-p_{1, n-1})\cdots (1-p_{1, k}) E_1 ``` > 具体的分析过程如下 ![](/media/content_img/graphDP01.png) ![](/media/content_img/graphDP02.png) ![](/media/content_img/graphDP03.png) ### 算法实现 核心思想是,将一个点$$to$$加入到 dijkstra 路径之后,会对其他路径仍为$$\infty$$的点(还没被选入的点)产生什么影响? 假设其他**未选进来**的点是$$k$$,$$to$$的加入会对$$k$$产生一些影响 * $$k$$这个点走向$$to$$的期望,这种策略考虑$$k$$这个点只走向$$to$$,并且在$$to$$停留 这种策略的期望时间记为$$up_k$$,并且$$up_k = wait_k \cdot p(k, to) \cdot E(to)$$ $$wait_k$$表示$$k$$这个点**其他路都走不通**,只能通往$$to$$,对应的概率 * $$to$$这个点的加入,就意味着**可能存在一条**$$k \to to$$的路径,那么这条路径就有**走不通的可能** 这样其他路都走不通的概率,$$wait_k \times = (1- p(k, to))$$ 要相应地更新 ```bash int main() { //.... vector<long double> E(n+1, inf), up(n+1, 0), wait(n+1, 1); vector<int> vis(n+1, 0); E[n] = 0; for (int i = 1; i <= n; i++) { long double mx = inf; int to = -1; for (int k = 1; k <= n; k++) { if (!vis[k] && chmin(mx, E[k])) to = k; } vis[to] = 1; if (to == 1) { printf("%.15Lf\n", E[1]); return 0; } for (int k = 1; k <= n; k++) if (!vis[k]) { up[k] += 0.01 * E[to] * wait[k] * p[k][to]; wait[k] *= (1 - 0.01 * p[k][to]); if (fabs(1 - wait[k]) > eps) E[k] = (1 + up[k]) / (1- wait[k]); } } } ```
0
0
上一篇:计数动态规划
下一篇:codeforces上的dp题(一)
看完文章有啥想法
发布评论
142 人参与,0 条评论