2018年杭电复试笔试最后一题(洛谷 P1550 浇水)
题目:
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
分析:
也是看了大佬的解释才懂的,然后自己写了一遍。
使用prim算法,把挖井这个动作看成一个结点,每个田看成一个结点,这样就构成了一个N+1个结点的最小生成树的问题了。
#include<cstdio>
#include<iostream>
#define MAX 101
using namespace std;
struct node{
double lowcost; //结点的当前最小花费
int adj; //使得结点花费最小的当前相邻结点
bool isin; //标记结点是否已经加入到生成树当中
}Node[100];
double cost[MAX][MAX]={INT_MAX};
int N;
void input(void){
cout<<"please input the number of fields"<<endl;
cin>>N;
cout<<"输入各个田打井的费用:"<<endl;
for(int i=1;i<=N;++i){
cin>>cost[0][i];
}
cout<<"输入田之间的花费:"<<endl;
for(i=1;i<=N;++i)
for(int j=1;j<=N;++j)
cin>>cost[i][j];
cout<<"输入完毕。"<<endl;
}
void prim(void){
double min=INT_MAX, sum=0;
int index;
Node[0].isin=true;
for(int i=1;i<=N;i++){
Node[i].adj=0;
Node[i].lowcost=cost[0][i];
}
for(int t=1;t<=N;++t){
min=INT_MAX;
for(i=1;i<=N;++i)
if(!Node[i].isin && Node[i].lowcost < min){ // 从未添加的结点中找到与已添加结点cost最小的那一个
index=i;
min=Node[i].lowcost;
}
cout<<"node "<<index<<" added"<<endl;
sum+=min;
Node[index].isin = true; //将其加入已添加的结点集合中
for(int j=1;j<=N;++j)
if(Node[j].lowcost > cost[index][j]){
Node[j].lowcost = cost[index][j];
Node[j].adj = index; // 更新相连接点,使得与生成树中已经添加结点的cost最小
}
}
cout<<sum<<endl;
}
int main()
{
input();
prim();
return 0;
}
运行结果: