Day4 省集赛后总结

· · 个人记录

刚 T1。

前 1h 想偏了，在不对的做法上想。

但是也有一定启发，随后找出了一个结论，但是过了 10min 发现不完全正确（仅仅在图是一棵树的情况下成立，但是题目给定的图多了一条边）。

然后经过分类讨论，修正，成功找出了正确结论，即设非环上边权最小为 a，环上边权最小和次小分别是 b,c，那么 S = min(a,b+c)，并快速证明。

然后我在基环树上如何找出环上的边上卡了 10min，写了个两次 dfs 搞定。

对于询问，想到了可以二分答案，直接判定就行了。

随之我在文档里写出了本题程序流程图。

并完成了大部分程序。

很遗憾最后的部分（对于 b,c 的处理）由于思路混乱，当时已经想出了该部分正确的分类讨论方法，也没能确定正确性，然后就这一部分一直放着没写。

看着时间不太够用，T2 写了个 dijkstra，连样例都没测就交了。

最后本场比赛爆零。

赛后看题解，发现 T1 思路和题解几乎一样。

T2 等会再写。