寒鸽儿のBlog

期望得分 100+100+60 = 260
实际得分 30+20+70 = 120

看到很多神仙都是一顿A* / 双向广搜 等操作。
其实状态数也没那么多

tarjan缩点后形成一个DAG

在有向图中,边又没啥限制,因而考虑缩点。缩点的同时记录该点内部有无酒吧以及该点的总钱数。

$m = n-1$
贪心dfs,按照结点编号较小的输出即可。
$60pts$到手
$m = n$
这不就是一棵基环树嘛?

欧拉回路拆环

偶数度数 --> 欧拉回路
两个奇数度数 --> 普通欧拉回路

考虑缩点。

到现在才来学强连通分量QaQ

$f(x) = min\{a[k]\}, k \in [x-m+1, x]$