【BZOJ 1937】[SHOI2004] Mst最小生成树

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1937
神犇题解:https://blog.sengxian.com/solutions/bzoj-1937

解题报告

我们首先可以得到一个结论:$T$中的边的边权只会减少,其他边的边权只会增加
于是我们将$T$中的边放在左边,其他边放在右边,都作为二分图的点,点权为边权
然后左右两两连边,边权$v_i$为右边点的权值减左边点的权值

此时问题转化为,每一个点设一个$d_i$,满足二分图中任意一条边$i \to j$满足$v_{i \to j} \le d_i + d_j$,求最小化$\sum{d_i}$
这是$KM$算法的关键步骤。于是直接上$KM$算法就可以了

但我不会$KM$算法
←为什么这个频率这个鬼畜啊 QwQ

但不会$KM$算法我们也能做,回忆$KM$算法顶标的作用
最小的顶标和就是最大权匹配的权值和
于是我们用费用流增广这个二分图,直到增广到权值为负就可以了

14 thoughts to “【BZOJ 1937】[SHOI2004] Mst最小生成树”

  1. 912971 558837Hey there guys, newbie here. Ive lurked about here for slightly whilst and thought Id take part in! Looks like youve got quite a excellent spot here 917471

  2. 687628 355233Effectively written articles like yours renews my faith in todays writers. Youve written information I can finally agree on and use. Thank you for sharing. 806221

  3. 3520 3093Thanks for the post. I like your writing style – Im trying to start a blog myself, I feel I may well read thru all your posts for some suggestions! Thanks once more. 25247

  4. You actually make it appear so easy together with your presentation but I find this matter to be really one thing which I think I’d never understand. It kind of feels too complex and very broad for me. I am having a look ahead on your subsequent put up, I’ll attempt to get the hold of it!

Leave a Reply

Your email address will not be published. Required fields are marked *