本文共 1281 字,大约阅读时间需要 4 分钟。
题目描述
Farmer John has decided to bring water to his N (1 <= N <= 300) pastures which are conveniently numbered 1…N. He may bring water to a pasture either by building a well in that pasture or connecting the pasture via a pipe to another pasture which already has water. Digging a well in pasture i costs W_i (1 <= W_i <= 100,000). Connecting pastures i and j with a pipe costs P_ij (1 <= P_ij <= 100,000; P_ij = P_ji; P_ii=0). Determine the minimum amount Farmer John will have to pay to water all of his pastures. POINTS: 400 农民John 决定将水引入到他的n(1<=n<=300)个牧场。他准备通过挖若 干井,并在各块田中修筑水道来连通各块田地以供水。在第i 号田中挖一口井需要花费W_i(1<=W_i<=100,000)元。连接i 号田与j 号田需要P_ij (1 <= P_ij <= 100,000 , P_ji=P_ij)元。 请求出农民John 需要为使所有农场都与有水的农场相连或拥有水井所需要的钱数。 注意是最少的钱数,这点题目没讲清
输入输出格式
输入格式: 第1 行为一个整数n。 第2 到n+1 行每行一个整数,从上到下分别为W_1 到W_n。 第n+2 到2n+1 行为一个矩阵,表示需要的经费(P_ij)。
输出格式:
只有一行,为一个整数,表示所需要的钱数。
输入输出样例
输入样例#1: 4 5 4 4 3 0 2 2 2 2 0 3 3 2 3 0 4 2 3 4 0 输出样例#1: 9
这段代码教会我,首先不要把数组啦这些东西的名字取一样,不然会搞错的,其次就是Int[int]在c++中不不被允许的
#include#include #include using namespace std;//最小生成树之kruskal 也就是使用并查集//这个问题是需要求解最小钱的数量,而这里面,点是需要钱的,而边也是需要钱的//看到网上一个思路,太绝了,把打井的这个值,当做是从起始点0到打井点的距离,所以就可以将所有的点都和在一起讨论了//创建一个结构体数组struct J{ int x,y,z;//分别代表起始点,终点,和距离}j[100];//写一个比较的方法bool cmp(J a,J b){ return a.z
转载地址:http://rkfen.baihongyu.com/