【题解】[APIO2023] 赛博乐园 / cyberland

P9370 [APIO2023] 赛博乐园 / cyberland - 洛谷 (luogu.com.cn)好题。follow the eternal Magnetic flow,decode the endless Enigma below.1.分层有特殊减少贡献的限制次数试试分层最短路。arr[i]0意思是这个国家可以让当前总通过时间为 0。这种点和起点没区别跑多源最短路就行。arr[i]2表示这个国家拥有让当前总通行时间除以 2 的能力。这种能力只能使用次注意到大多数数据可以从这里入手。遇到一个点贡献直接除以肯定是不满足正常最短路的正确性的相当于图中有负环。但发现多的能力使用次数的状态无法影响较少的能力使用次数的状态。也就是状态们在同一层时优先选走费用少的。不在同一层时优先走层数少的。好了现在解决的情况了。这个分数的占比非常大近乎是正解所以正解肯定差不多。注意到边数 * 边权。而这个数除以到精度以下。也就是最大就够用了。#include cyberland.h #includebits/stdc.h using namespace std; const int N 7e5 10; struct node { int x; double c; int k; }; vectornode G[N]; bool operator(node na, node nb) { if (na.k nb.k) return na.c nb.c; return na.k nb.k; } priority_queuenode Q; bool v[N], vis[80][N]; double dis[80][N]; void dfs(int x, int ed) { v[x] 1; for (node no : G[x]) { int y no.x; if (!v[y] y ! ed) { dfs(y, ed); } } } void init(int n, int K) { while (!Q.empty()) Q.pop(); for (int i 0; i n; i) { v[i] 0; G[i].clear(); } for (int i 0; i K; i) { for (int j 0; j n; j) { dis[i][j] 1e17; vis[i][j] 0; } } } double solve(int n, int m, int K, int ed, vectorint x, vectorint y, vectorint c, vectorint arr) { K min(K, 70); init(n, K); for (int i 0; i m; i) { G[x[i]].push_back({y[i], (double)c[i], 0}); G[y[i]].push_back({x[i], (double)c[i], 0}); } dfs(0, ed); // 多源初始化 for (int i 0; i n; i) { if (v[i] (arr[i] 0 || i 0)) { dis[0][i] 0; Q.push({i, 0.0, 0}); } } while (!Q.empty()) { node no Q.top(); Q.pop(); int u no.x, k no.k; if (vis[k][u] || u ed) continue; vis[k][u] 1; for (node e : G[u]) { int v e.x; double w e.c; if (dis[k][v] dis[k][u] w) { dis[k][v] dis[k][u] w; if (!vis[k][v]) { Q.push({v, dis[k][v], k}); } } if (arr[v] 2 k K) { if (dis[k 1][v] (dis[k][u] w) / 2.0) { dis[k 1][v] (dis[k][u] w) / 2.0; if (!vis[k 1][v]) { Q.push({v, dis[k 1][v], k 1}); } } } } } double ans DBL_MAX; for (int i 0; i K; i) { ans min(ans, dis[i][ed]); } if (ans 1e15) return -1; return ans; }2.倒推一个比较新颖的思路。最短路的本质是贡献必须不断递增不一定要严格递增。而这道题的倒着走就符合遇到 arr[i]2 的点就到下一层而第 k 层边的贡献就要除以。arr[i]0 就到 K 1 层全部边的费用都是 0。总的来说很有意思的一道多层最短路复合题做完感觉对这个算法的了解更深。#include cyberland.h #includebits/stdc.h using namespace std; const int N 7e5 10; struct node { int x; double c; int k; }; vectornode G[N]; // 反向思路用裸 Dijkstra只按距离排序 bool operator(node na, node nb) { return na.c nb.c; } priority_queuenode Q; bool vis[80][N]; double dis[80][N]; double num[80]; void init(int n, int K) { // 预计算边权倍数 num[0] 1.0; for (int i 1; i K; i) { num[i] num[i - 1] / 2; } num[K 1] 0; // 手动更改一下第 K 1 层的权重 while (!Q.empty()) Q.pop(); for (int i 0; i n; i) { G[i].clear(); } for (int i 0; i K 1; i) { for (int j 0; j n; j) { dis[i][j] 1e17; vis[i][j] 0; } } } double solve(int n, int m, int K, int ed, vectorint x, vectorint y, vectorint c, vectorint arr) { K min(K, 70); init(n, K); for (int i 0; i m; i) { G[x[i]].push_back({y[i], (double)c[i], 0}); G[y[i]].push_back({x[i], (double)c[i], 0}); } // 从 ed 出发目标到 0 dis[0][ed] 0; Q.push({ed, 0.0, 0}); while (!Q.empty()) { node no Q.top(); Q.pop(); int u no.x, k no.k; if (vis[k][u]) continue; vis[k][u] 1; for (node e : G[u]) { int v e.x; if (v ed) continue; // 不能走回来 double w e.c; if (arr[v] 0) { if (dis[K 1][v] dis[k][u] w * num[k]) { dis[K 1][v] dis[k][u] w * num[k]; if (!vis[K 1][v]) { Q.push({v, dis[K 1][v], K 1}); } } continue; // 清零后不再尝试其他转移 } if (dis[k][v] dis[k][u] w * num[k]) { dis[k][v] dis[k][u] w * num[k]; if (!vis[k][v]) { Q.push({v, dis[k][v], k}); } } if (arr[v] 2 k K) { if (dis[k 1][v] dis[k][u] w * num[k]) { dis[k 1][v] dis[k][u] w * num[k]; if (!vis[k 1][v]) { Q.push({v, dis[k 1][v], k 1}); } } } } } // 答案取所有层到达 0 的最小值 double ans DBL_MAX; for (int i 0; i K 1; i) { ans min(ans, dis[i][0]); } if (ans 1e15) return -1; return ans; }