ZigZagK

Never give up fighting!

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

题目概述

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

解题报告

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

示例程序

点赞
  1. 访客zzs说道:

    太强了Orz

     Google Chrome 66.0.3359.139   Linux
    回复
    1. 博主ZigZagK说道:
      @zzs

      您才是真大佬啊Orz

       Google Chrome 66.0.3359.139   Linux
      回复

发表评论

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

不资瓷Markdown;资瓷LaTeX:行内公式\(...\),行间公式\[...\]