2022.10.15
练习情况
P2073 送花
按照题意模拟，二分最贵最便宜删除。
Code:
P2073
P4560 [IOI2014]Wall 砖墙
线段树，下传标记时注意取最大和取最小。
Code:
P4560
P5905 【模板】Johnson 全源最短路
板子
P1266 速度限制
分层图最短路，到达每个点的速度，并记录路径。
Code:
P1266
P5304 [GXOI/GZOI2019]旅行者
正解是正反图跑两次 \(Dijkstra\)
非正解：
跑 \(k\) 次 \(Dijkstra\) ，在最短路时优化。
- 当第一个不是起点但包含在 \(k\) 个的点出现，更新答案并退出。
- 当优先队列里点的 \(dis\) 大于等于答案退出。
- 控制循环层数（不然会 \(T\) #11 ）
Code:
居然还跑到了最优解
数据过水
P4001 [ICPC-Beijing 2006] 狼抓兔子
最小割 \(=\) 最大流
\(Dinic\) 板子，注意是无向边，两边权值都为 \(w\) 。
Code:
P4001