氵一篇 Blog
Shq 只会刷水题了 /kel
1601. [Usaco2008 Oct]灌水
Description
Farmer John 已经决定把水灌到他的 块农田,农田被数字 到 标记。把一块土地进行灌水有两种方法,从其他农田饮水,或者这块土地建造水库
建造一个水库需要花费 , 连接两块土地需要花费. 计算 Farmer John 所需的最少代价。
Input
*第一行:一个数
*第二行到第 行:第 行含有一个数
*第 行到第 行:第 行有 个被空格分开的数,第 个数代表
Output
*第一行:一个单独的数代表最小代价.
Sample Input
1 | 4 |
Sample Output
1 | 9 |
输出详解:
Farmer John在第四块土地上建立水库,然后把其他的都连向那一个,这样就要花费
题解
sb 最小生成树题
建一个点向所有点连一条权值为 的边
剩下的按照题目来就好了(
Code
1 | struct Edge { |
谜之音:那么氵的题目还氵 Blog(
本文是 2019/1/9 20:58 写完的,不知道啥时候能发出去(