ZigZagK

Never give up fighting!

[最大权闭合图]BZOJ1497(NOI2006)【最大获利】题解

题目概述

\(n\) 个点 \(m\) 条边,每个点需要花费 \(p_i\) 购买,每条边可以得到 \(c_i\) 的价值。现在要购买一些点,如果一条边两端的点都被购买了,就可以得到这条边的价值。求最大价值。

解题报告

如果一条边要得到价值,那么这条边的两端必须选,这就是闭合图的要求。所以我们把每条边也当成点,然后建图,刷最大权闭合图就行了。

示例程序

点赞
    1. ZigZagK说道:

      您才是真大佬啊Orz

发表评论

电子邮件地址不会被公开。 必填项已用*标注