国庆集训 DAY3 总结

_Cheems · 2023-10-06 16:02:43 · 个人记录

DAY2 没测题，嘿嘿嘿。

T1：缩点后求哪个联通块可被所有点到达，dfs一遍即可。

T2：缩点 + 选课。

T3：缩点后最短路（拓扑序上递推即可）。

T4：看这里。

T5： 直接做不好，那么由图的形态逐层往上思考。

• 链：显然一条链就是最大半连通子图，问题一就是总点数，问题二显然是 1。

• DAG：考虑拓扑排序找最长链，定义 f_u,g_u 分别为以 u 结尾的最长链长度 / 方案数，直接维护即可。

• 一般图：缩点后当作 DAG 处理即可。