ExaWizards 2019 F
没记到,淦。
CF773D
有一个 $n$ 个点的完全图,每两个点之间有一条长度为 $w_{i,j}$ 的无向边。构造以 t 为根的生成树,使得树上每个节点到根最短边的长度和最小。
对于每个 \(t\) 求答案。
\(n \le 2000\)。
把所有边减去最小的权值,设最小的边的一端为 x,于是转化成求 x 到 t 一条链的权值。
又可以发现,一定可以构造出一种最优情况,使链上的点从与最小边相连的点到 e 是 依次递增的。
这个结论可以用反证法证明:
如果链上有一条递减的边,那么把这条边放到链的起始位置答案肯定不劣,
因为前面较大的边并不会对链上的代价作出任何贡献.
由于链上的边权依次递增,每条边都只会作出一次贡献,相当于是一条 路径.
所以我们从与最小边相连的点 s 出发跑一遍最短路就可以计算得到。
跑 dj 松弛即可。
CF843D
给定一个有向图,q 次操作
- 询问 1 到 t 的最短路
- 将一些边的边权+1
\(n,m\le 10^5, q\le 2000, \sum|s_i|\le 10^6\)
标签:le,21,最小,课上,2023.7,权值 From: https://www.cnblogs.com/eggome/p/17571257.html