- D16 Tarjan vDCC缩点
点双连通分量缩点(vDCC)。
3 min read zh - D17 Dinic最大流
Dinic 最大流:分层图 + 阻塞流。
3 min read zh - D18 最小费用最大流EK
最小费用最大流:EK + SPFA 增广。
4 min read zh - D19 二分图最大匹配
二分图最大匹配:匈牙利算法。
4 min read zh - D20 树的直径
树的直径:两次 DFS/BFS 求最远点对。
3 min read zh - D21 树的重心
树的重心:删去后最大子树最小。
3 min read zh - D22 Kruscal重构树
Kruscal 重构树:最小瓶颈 / 连通性离线问题。
4 min read zh - D23 2-SAT
2-SAT:变量拆点 + Tarjan 强连通判定与构造。
4 min read zh - D24 2-SAT-前缀优化建图
2-SAT 前缀优化建图:每部分恰选一个 + 边至少一端选。
5 min read zh