把每块圆盘看成「木桩×圆盘种类」的带权点,相交或相切即连边,触底盘与触顶盘分别当源点和汇点,跑一遍点权 Dijkstra 求最小花费。
OJ: roj
题目 ID: 1719
难度:提高+/省选-
标签:图论最短路计算几何python
创建: 2026-10-07 18:50
更新: 2026-10-07 18:50
形式化题目
河是平面直角坐标系里
每买一块圆盘,必须把它的圆心放在某个木桩上(同一木桩上可以放任意多块,圆盘允许伸出河面,
即圆盘上
EE 只能在直线
求一组购买的圆盘(每个元素是"某个木桩 + 某种圆盘"),使得底边与顶边连通,且总价最小;
不存在这样的方案时输出 impossible。
规模:
正解
思路
第一步:把"买一堆盘"化简成"一条链"。
设买下的圆盘集合是
底边与顶边连通,当且仅当存在一条底边到顶边的路径
第二步:点权最短路。
把节点定成
,若 (这块盘触底); ,若 (两块盘相交或相切); ,若 (这块盘触顶)。
答案就是
答案
这里必须把状态定成"木桩 + 种类"而不是"某一条边",是因为同一块盘可以同时接住前后两段:
走到木桩
第三步:距离全部用整数。 浮点开方在 isqrt / sqrtl 加一步修正,全程整数),判定就完全精确了。
第四步:Pareto 压缩圆盘种类。 如果存在另一种盘
第五步:让每个状态只被松弛一次。 直接枚举转移是
关键观察是:松弛的结果
于是维护
第六步:无解与提前退出。 出堆时如果 break。堆空了还没触顶,输出 impossible。
以样例第 1 组为例(
| 顺序 | 木桩坐标 | 圆盘 |
累计花费 |
|---|---|---|---|
| 1(触底) | 1 | ||
| 2 | 2 | ||
| 3 | 102 | ||
| 4 | 103 | ||
| 5 | 104 | ||
| 6 | 105 | ||
| 7 | 106 | ||
| 8(触顶) | 206 |
impossible。
代码
Python 版:
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 18:50
# update_at: 2026-10-07 18:50
import sys
from bisect import bisect_left
from heapq import heappop, heappush
from math import isqrt
INF = 10 ** 18 # 最短路无穷大:远大于任何可行花费(<= 250 * 10^6)
# 类型别名(Python 3.12+ 的 type 语句),相当于 C++ 的 using / typedef
type Pile = tuple[int, int] # 木桩坐标 (X, Y)
type Disk = tuple[int, int] # 圆盘种类 (R, C),半径与价格
def ceil_sqrt(s: int) -> int:
"""返回最小的 r 使 r*r >= s,即圆心距的整数向上取整。"""
r = isqrt(s)
return r if r * r >= s else r + 1
def pareto_front(disks: list[Disk]) -> tuple[list[int], list[int]]:
"""把圆盘种类压成 Pareto 前沿,返回(半径表, 价格表),两者都升序。
"半径更大且价格不更高"的种类可以完全替代另一种(够得更远还更便宜),
故只保留不被支配的:按半径从大到小扫,价格必须比所有更大半径的种类都低才留下。
"""
cheapest = {} # 半径 -> 该半径下的最低价格
for radius, cost in disks:
if cost < cheapest.get(radius, INF):
cheapest[radius] = cost
radii: list[int] = []
costs: list[int] = []
floor = INF # 已保留种类(半径都比当前这个大)中的最低价格
for radius in sorted(cheapest, reverse=True):
if cheapest[radius] < floor: # 半径更小却更便宜,才没被支配
radii.append(radius)
costs.append(cheapest[radius])
floor = cheapest[radius]
radii.reverse() # 翻成半径升序,价格随之升序
costs.reverse()
return radii, costs
def cheapest_bridge(piles: list[Pile], disks: list[Disk], river_w: int) -> int | None:
"""返回从 y=0 走到 y=W 的最小花费,无解返回 None。
节点 = (木桩, 圆盘种类),节点权 = 圆盘价格:所有触底盘是源点、任意触顶盘是终点,
于是答案就是从地面到河对岸的点权最短路。
"""
bl = bisect_left # 内层循环要跑 10^7 次,绑定成局部名省一次全局查找
radii, costs = pareto_front(disks)
n, p = len(piles), len(radii)
# 圆心距向上取整:d <= r1 + r2 等价于 ceil(d) <= r1 + r2,全程整数比较
gap = [[ceil_sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2) for x2, y2 in piles] for x1, y1 in piles]
frontier = [p] * n # 木桩 k 上 [frontier[k], p) 已定最短路,前面还待松弛
dist = [[INF] * p for _ in range(n)]
heap: list[tuple[int, int, int]] = []
live = list(range(n)) # frontier > 0 的木桩:只有它们还有待松弛的圆盘
def relax(k: int, idx: int, base: int) -> None:
"""用花费 base 松弛木桩 k 上尚未定最短路的圆盘 [idx, frontier[k])。
出堆的 base 单调不减、松弛结果 base + 价格对 base 单调,
所以每个 (木桩, 圆盘) 状态第一次被覆盖时拿到的就是它的最终最短路。
"""
for t in range(idx, frontier[k]):
dist[k][t] = base + costs[t]
heappush(heap, (dist[k][t], k, t))
frontier[k] = idx
if idx == 0:
live.remove(k) # 整根木桩都定完了,退出活跃表
for k, (_, y) in enumerate(piles):
relax(k, bl(radii, y), 0) # 源点:半径 >= Y_k 的圆盘触底,代价 0 起
while heap:
cost, i, a = heappop(heap)
if cost != dist[i][a]:
continue
if radii[a] >= river_w - piles[i][1]:
return cost # 该盘触顶,出堆顺序保证这就是最小花费
row, shift = gap[i], -radii[a] # 跳到木桩 k 需要半径 >= 圆心距 - R_a
for k in live[:]: # 快照遍历:relax 会把定完的木桩移出 live
idx = bl(radii, row[k] + shift)
if idx < frontier[k]:
relax(k, idx, cost)
return None
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
out: list[str] = []
test_count = next(data)
for _ in range(test_count):
n, m = next(data), next(data)
river_w = next(data)
piles: list[Pile] = [(next(data), next(data)) for _ in range(n)]
disks: list[Disk] = [(next(data), next(data)) for _ in range(m)]
best = cheapest_bridge(piles, disks, river_w)
out.append('impossible' if best is None else str(best))
print('\n'.join(out))
if __name__ == "__main__":
solve()C++ 版(同一算法):
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-07 18:50
* update_at: 2026-10-07 18:50
*/
// main.cpp:过河(一本通 · 高手训练 1719)。
// 可行走集合 = 直线 y=0、直线 y=W 与买下的若干圆盘(含边界与内部)。
// 圆心必须放在某个木桩上,圆盘可以伸出河面(y<0 或 y>W)。
// 两圆盘能互相走到 ⇔ 圆心距 d <= r1 + r2(相切/相交即可);
// 圆盘触底 ⇔ Y <= R,触顶 ⇔ W - Y <= R。
// 于是问题化成"点权(圆盘价格)最短路":节点 = (木桩, 圆盘种类),节点权 = 圆盘价格,
// 所有触底的圆盘是源点(以 0 为初始代价),任意触顶的圆盘是终点。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 255; // 木桩数量上限,题面 N <= 250
const int MAXM = 255; // 圆盘种类上限,题面 M <= 250
const ll INF = 4000000000000000000LL; // 最短路无穷大,远大于任何可行花费(<= 250 * 10^6)
// 一根木桩:圆心只能放在这里,坐标 (x, y)
struct Pile {
ll x;
ll y;
};
// 一种圆盘:半径 r、单价 c
struct Disk {
ll r;
ll c;
};
// 堆中元素:停在木桩 pile 上、用的是第 disk 种圆盘时的总花费 cost
struct State {
ll cost;
ll pile;
ll disk;
// priority_queue 默认大根堆,这里反向比较,得到按 cost 的小根堆
bool operator<(const State &other) const { return cost > other.cost; }
};
int pileCnt; // 木桩数 N
int diskTypeCnt; // 读入的圆盘种类数 M
ll riverW; // 河的宽度 W
ll typeCnt; // 压缩后保留下来的圆盘种类数(Pareto 前沿长度),也当"种类下标"的上界用
Pile pile[MAXN]; // 木桩
Disk disk[MAXM]; // 保留的圆盘,半径升序、价格随之严格升序
ll pileDist[MAXN][MAXN]; // pileDist[i][k] = 木桩 i 与木桩 k 的圆心距向上取整(整数比较,免浮点误差)
ll dist[MAXN][MAXM]; // dist[i][a]:从地面一路走到"停在木桩 i 上的第 a 种圆盘"的最小花费
ll frontier[MAXN]; // 木桩 k 上下标 >= frontier[k] 的圆盘已定最短路,[0, frontier[k]) 还待松弛
priority_queue<State> pq; // 堆优化 Dijkstra 的优先队列
// 返回最小的整数 r >= 0 使 r*r >= s,即 ceil(sqrt(s));圆心距全程用整数表示
ll ceil_sqrt(ll s) {
if (s <= 0) return 0;
ll r = sqrtl(s); // 先取浮点近似,下面两个 while 把它修正成精确的整数开方
while (r > 0 && (r - 1) * (r - 1) >= s) r--;
while (r * r < s) r++;
return r;
}
// 读入 M 种圆盘并压缩成 Pareto 前沿:半径升序、价格严格升序。
// "半径更大且价格不更高"的种类可以完全替代另一种(够得更远、还更便宜),故只保留不被支配的。
void read_disks() {
map<ll, ll> cheapest; // 半径 -> 该半径下的最低价格,只为同半径去重
for (int i = 0; i < diskTypeCnt; i++) {
ll radius, cost;
scanf("%lld %lld", &radius, &cost);
map<ll, ll>::iterator it = cheapest.find(radius);
if (it == cheapest.end() || cost < it->second) cheapest[radius] = cost;
}
typeCnt = 0;
ll floor = INF; // 已保留种类(半径都比当前这个大)中的最低价格
for (map<ll, ll>::reverse_iterator it = cheapest.rbegin(); it != cheapest.rend(); ++it) {
if (it->second < floor) { // 半径更小却更便宜,才没被"更大更便宜的盘"支配
disk[typeCnt].r = it->first;
disk[typeCnt].c = it->second;
typeCnt++;
floor = it->second;
}
}
reverse(disk, disk + typeCnt); // 翻成半径升序,价格随之升序
}
// 二分出第一个半径 >= need 的种类下标:半径表升序,故"半径够用"的种类恰好是一段后缀
ll lower_bound_radius(ll need) {
ll lo = 0, hi = typeCnt; // 答案落在 [lo, hi],hi 表示"没有种类够用"
while (lo < hi) {
ll mid = (lo + hi) / 2;
if (disk[mid].r >= need) hi = mid;
else lo = mid + 1;
}
return lo;
}
// 用花费 base 一次性松弛木桩 k 上尚未定最短路的圆盘 [idx, frontier[k])。
// 每次出堆的 base 单调不减,而松弛结果 base + c 对 base 单调,
// 所以每个 (木桩, 圆盘) 状态第一次被覆盖时拿到的就是它的最终最短路。
void relax_pile(ll k, ll idx, ll base) {
for (ll t = idx; t < frontier[k]; t++) {
dist[k][t] = base + disk[t].c;
State cur;
cur.cost = dist[k][t];
cur.pile = k;
cur.disk = t;
pq.push(cur);
}
frontier[k] = idx;
}
int main() {
int testCnt;
if (scanf("%d", &testCnt) != 1) return 0;
while (testCnt--) {
scanf("%d %d %lld", &pileCnt, &diskTypeCnt, &riverW);
for (int i = 0; i < pileCnt; i++) scanf("%lld %lld", &pile[i].x, &pile[i].y);
read_disks();
// 圆心距预处理:ceil(两点欧氏距离)。d <= r1 + r2 等价于 ceil(d) <= r1 + r2
for (int i = 0; i < pileCnt; i++) {
for (int k = 0; k < pileCnt; k++) {
ll dx = pile[i].x - pile[k].x;
ll dy = pile[i].y - pile[k].y;
pileDist[i][k] = ceil_sqrt(dx * dx + dy * dy);
}
}
while (!pq.empty()) pq.pop();
for (int k = 0; k < pileCnt; k++) {
frontier[k] = typeCnt; // 一开始所有圆盘都没定最短路
for (ll t = 0; t < typeCnt; t++) dist[k][t] = INF;
}
// 源点:能触底的圆盘(Y_k <= R),代价就是这块圆盘的价格
for (int k = 0; k < pileCnt; k++) relax_pile(k, lower_bound_radius(pile[k].y), 0);
ll ans = -1;
while (!pq.empty()) {
State cur = pq.top();
pq.pop();
if (cur.cost != dist[cur.pile][cur.disk]) continue;
if (disk[cur.disk].r >= riverW - pile[cur.pile].y) { // 这块圆盘触顶了
ans = cur.cost;
break; // 出堆顺序单调不减,首次触顶即最优
}
for (int k = 0; k < pileCnt; k++) {
if (frontier[k] == 0) continue; // 木桩 k 上已无可松弛的圆盘
// 从当前圆盘跳到木桩 k:需要半径 >= 圆心距 - R_cur,仍是一段后缀
ll idx = lower_bound_radius(pileDist[cur.pile][k] - disk[cur.disk].r);
if (idx < frontier[k]) relax_pile(k, idx, cur.cost);
}
}
if (ans < 0) printf("impossible\n");
else printf("%lld\n", ans);
}
return 0;
}复杂度
- 时间:预处理圆心距
;Dijkstra 中每个状态至多入堆一次,共 次出堆, 每次出堆对 根木桩各做一次二分,单组数据 , 共 。取 上界约 次内层操作, C++ 实测最坏数据点( problem9,组全连通但触不到顶、所有状态都要弹出)0.49 s, 限时 2000 ms。Python 版因为内层循环在解释器里跑,同一数据点约 2.0 s, 超出本题 2000 ms 的限时,属于"算法同阶但常数不够"的 TLE 风险(见 ## 总结)。 - 空间:圆心距矩阵
, 表 , 堆 ,单组数据约 ,取上界约 6.3 万个 long long加一个的距离矩阵, C++ 实测峰值 8.3 MB,限时内存 256 MB。 - Python 与 C++ 的关系:
main.py与main.cpp是同一算法、同一复杂度的两个实现, 只是 Python 版额外用live活跃表把"已经全部定完最短路的木桩"从内层循环里摘掉, 最坏数据点因此从 2.9 s 降到 2.0 s;C++ 版靠frontier[k] == 0的判断达到同样效果。 - 正确性验证:
main.cpp与main.py除逐点跑通素材的 10 个数据点外, 还与一份不剪枝的稠密版 Dijkstra(显式枚举所有点对、 )做了 1800 组随机小数据对拍,结果完全一致。
总结
- 先做模型化简,再谈算法:题目问的是"买一堆盘让两岸连通", 但连通只需一条路径,路径是任意方案的子集,于是最优化问题直接退化成最短路。 这一步把"选集合"的不确定性彻底消掉了。
- 节点权而不是边权:把状态定成"木桩 + 圆盘种类"、价格记在点上, 才能让中间木桩上那同一块盘同时接住前后两段而不重复计费。
- 单调性换来"每个状态只松弛一次":
对 单调, 配合出堆顺序单调不减,就能用"后缀 + frontier 收缩"把 的稠密转移压到 。这是本题最核心的一步,也是"堆优化 Dijkstra 中节点只会被最终确定一次"的典型用法。 - Pareto 剪枝顺手把二分做好了:删掉"更大更便宜"能支配的种类之后,
半径表升序、价格也升序,"半径至少
"自然变成一段后缀,二分和区间松弛都能直接用。 - 几何判定别碰浮点:
, 把圆心距向上取整成整数即可, 上到 也不会有精度风险。 - 数据说明:本题素材目录里带数据生成脚本(
data.py),说明测试数据是依据题面自造的, 题面本身也是从网络重建的(pic/1719.jpg无对应图片文件),出题意图与官方原题可能有细微偏差。 素材中的std.cpp与本文模型一致,10 个数据点全部与题面样例吻合,本文实现亦与它逐点一致。
【数据规模】
对于10%的数据,