BZOJ 1601 [Usaco2008 Oct] 灌水

发布于 2017-06-28  187 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1601

题意:把水灌到 n 块农田,把一块土地进行灌水有两种方法,从其他农田饮水,或者这块土地建造水库。 建造一个水库需要花费\(w_i\),连接两块土地需要花费\(P_{i,j}\),求所需的最少代价..


建立一个虚拟根节点,向所有点连水库费用,然后裸上最小生成树即可

 


一个非常弱的准退役OIER