P4177 [CEOI2008]order

题目链接

如果不考虑“租”，那么就是最大权闭合子图的板子题了。

现在考虑“租用”的情况，即：我们可以选择不遵守“闭合子图”的规定，但是一次要付出一些代价，那么我们就在我们的最大权闭合子图的板子中将原图的边容量改为租用单次费用即可。这样，割掉原图的边将成为可能，符合题意。