【题解】Solution Set - NOIP2024集训Day52 图论杂题2
【题解】Solution Set - NOIP2024集训Day52 图论杂题2
https://www.becoder.com.cn/contest/5628
「BZOJ4144」Petrol
和 「CF1253F」Cheap Robot 完全一样，只是需要特判一下不联通。
「AMPPZ2013」Bytehattan
注意：题目删的是双向边。
对偶图。
周冬 2008 年国家队论文
如果不连通，就是以 \((a,b)\) 作为源点/汇点，存在一个割，等价于在对偶图上存在一个环。
删去一条边，就是说我们可以割掉这条边，于是在对偶图上加上对应边，然后判是否能构成环就行了。
「CCO 2021」商旅(Travelling Merchant)
做过。
考虑一个 dp。
\[f_u=\min_v(\max(f_v-p,r))
\]
首先排除所有出度为 \(0\) 的点，其一定无解；否则一定可以有解。
想办法避免 dp 的后效性。
我们的目标其实就是想办法去掉里面的 \(\max\)。
根据一些性质分析。
注意到，性质 1：一条边的 \(r\) 如果是最大的话，她对 \(u\) 的贡献只能是 \(r\)（因为只要从这里走出去就畅通无阻了）。贡献后直接删除。
这个时候，我们可能产生一些没有出度的点，其答案一定是确定了，那么删掉她并用其去更新其前驱。
此时，所有的点都是有出度的了。
所以，刚才的性质 1 依旧适用，所以我们每次取 \(r\) 最大的边来破环就行了。
具体实现可以参见 luogu 题解区。
「JOI 2017 Final」足球
「COI2012」TRAMPOLIN
直接将每个点可以去到的点连有向边，然后就是求最长路。
蹦床的话，就建一个虚点连向所有的点就行了。
最后缩点，然后 topo 就行了。
4min