[AcWing 340] 通信线路
2022/8/11 6:23:01
本文主要是介绍[AcWing 340] 通信线路,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
二分 + 双端队列广搜
复杂度 \(m \cdot log(r - l) = 1 \times 10^4 \times log(10^9) = 3 \times 10^5\)
点击查看代码
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N = 1e6 + 10; const int M = 1e3 + 10; const int INF = 0x3f3f3f3f; int n, m, k; int h[N], e[N], ne[N], w[N], idx; int d[M]; bool st[M]; void add(int a, int b, int c) { e[idx] = b; w[idx] = c; ne[idx] = h[a]; h[a] = idx ++; } bool check(int x) { deque<int> q; memset(d, 0x3f, sizeof d); memset(st, false, sizeof st); q.push_back(1); d[1] = 0; while (q.size()) { auto t = q.front(); q.pop_front(); if (st[t]) continue; st[t] = true; for (int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; int dist = w[i] > x; if (d[j] > d[t] + dist) { d[j] = d[t] + dist; if (!dist) q.push_front(j); else q.push_back(j); } } } return d[n] <= k; } void solve() { cin >> n >> m >> k; memset(h, -1, sizeof h); for (int i = 0; i < m; i ++) { int a, b, c; cin >> a >> b >> c; add(a, b, c); add(b, a, c); } int l = 0, r = 1e9; while (l < r) { int mid = l + r >> 1; if (check(mid)) r = mid; else l = mid + 1; } if (l > 1e6) cout << "-1" << endl; else cout << l << endl; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); solve(); return 0; }
- 抽象问题
可以将不超过 \(k\) 条路的长度置为 \(0\),在这样的前提下,求从起点到终点的一条路径,让这条路径上每段路径的最大值最小 - 二分
由于要求的是最大值最小,可以考虑用二分,下面考虑如何设置 \(check\) 函数,可以将二分的目标定为:将长度超过 \(x\) 的路径长度置为 \(0\),求能满足置为 \(0\) 的路径的条数小于等于 \(k\) 的情况下的最小值,将 \(check\) 函数设置为:是否满足在阈值设置为 \(x\) 的条件下,存在一条从起点到终点,经过长度超过 \(x\) 的边的个数不超过 \(k\) 的一条路径,如果存在,就让 \(r = mid\),否则,就让 \(l = mid + 1\),在这样的情况下,最终二分的结果就是在满足条件的情况下 \(x\) 所能取到的最小值,其余的没有置为 \(0\) 的路径的最大值为 \(x\),也就是最优解 - 双端队列广搜
在阈值 \(x\) 确定的情况下,要判断是否存在一条从起点到终点,经过长度超过 \(x\) 的边的个数不超过 \(k\) 的一条路径,可以将所有长度大于 \(x\) 的边权值设为 \(1\),其余边的权值设为 \(0\),问题就转化为求从起点到终点的最短路,判断最短距离是否不超过 \(k\),对于 \(0\) 和 \(1\) 两种边权的问题,可以用双端队列广搜,将边权为 \(0\) 的边放到队头,边权为 \(1\) 的边放到队尾,做一遍 \(BFS\) 即可 - 二分的区间
左端点 \(l\) 设置为 \(0\),因为 \(0\) 是有可能取到的,也就是全部免费的情况,右端点 \(r\) 设置为 \(10^9 > 10^6\),因为路径的长度 \(L\) 最大为 \(10^6\),可以用大于 \(10^6\) 的数来代表无解的情况(双端队列广搜时,如果不连通,\(d[n]\) 就一直是正无穷,也就是 \(check\) 一直是 \(false\),最后 \(l\) 会跑到 \(r\) 的位置)
这篇关于[AcWing 340] 通信线路的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升
- 2024-05-08代码报错不用愁,CodeGeeX一键完成代码修复、错误解释的功能上线了!
- 2024-05-08今天开始程序员不用再发愁写commit message了,全部由CodeGeeX自动完成!