2020-2021:teams:legal_string:jxm2001:支配树
差别
这里会显示出您选择的修订版和当前版本之间的差别。
|
2020-2021:teams:legal_string:jxm2001:支配树 [2021/07/30 20:12] jxm2001 创建 |
2020-2021:teams:legal_string:jxm2001:支配树 [2021/07/30 20:18] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 123: | 行 123: | ||
| 给定一个无向连通图，定义源点为 $1$ 号点。对每条边，询问删除该边会导致源点到多少个点的最短路改变。 | 给定一个无向连通图，定义源点为 $1$ 号点。对每条边，询问删除该边会导致源点到多少个点的最短路改变。 | ||
| + | |||
| + | === 题解 === | ||
| 首先跑最短路，然后保留所有在最短路树上的边，同时规定每条边方向由距离近的点指向距离远的点，易知构成有向无环图。 | 首先跑最短路，然后保留所有在最短路树上的边，同时规定每条边方向由距离近的点指向距离远的点，易知构成有向无环图。 | ||
2020-2021/teams/legal_string/jxm2001/支配树.1627647145.txt.gz · 最后更改: 2021/07/30 20:12 由 jxm2001
