杭电2018复试上机真题（第三题更新）

ps：题是别的地方copy过来的，代码是自己的

第三题没时间写注释了，先这样吧

第一题:

杭电2018复试上机真题（第三题更新）

第二题:

杭电2018复试上机真题（第三题更新）

第三题:

瓜农王大爷去年种西瓜赚了不少钱。看到收入不错，今年他又重新开辟了n个西瓜地。
为了能给他的n个西瓜地顺利的浇上水，对于每个西瓜地他可以选择在本地打井，也可以修管道从另一个瓜地（这个瓜地可能打了井；也可能没打井，他的水也是从其他瓜地引来的）将水引过来。
当然打井和修管道的费用有差别。已知在第i个西瓜地打井需要耗费wi元，在第i、j个西瓜地之间修管道需要耗费pi,j元。
现在的问题是：王大爷要想使所有瓜地都被浇上水，至少需要花费多少钱（打井与修管道的费用和）？
由于瓜地较多，王大爷无法选择在哪些（个）瓜地打井，哪些西瓜地之间修管道。
请你编程帮王大爷做出决策，求出最小费用。

（1<=N<=300，1<=wi<=100000；pi,i=0，1<=pi,j=pj,i<=100000）

input

第1行，一个正整数n，代表西瓜地的数量。
以下n行，依次给出整数w1..wn（每块西瓜地的打井费用）。
紧接着是一个n*n的整数矩阵，矩阵的第i行第j列的数代表pi,j（两块西瓜地之间建立管道的费用）。每行的两个数之间有一个空格隔开。

6
5
4
4
3
1
20
0 2 2 2 9 9
2 0 3 3 9 9
2 3 0 4 9 9
2 3 4 0 9 9
9 9 9 9 0 9
9 9 9 9 9 0

output

在第4个瓜地打井（费用为3），然后将第2,3，4个瓜地与第1个瓜地间修管道（费用分别是2,2,2），这样水可以经过管道从4流向1，然后经1再流向2和3；
在第5个瓜地打井（费用为1），5和6之间修管道（费用为9）。
这样一共打了2口井，修了4条管道，能给所有的6个瓜地浇水，费用是：3+2+2+2+1+9=19。

杭电2018复试上机真题（第三题更新）

#include<cstdio>
#include<algorithm>

using namespace std;

int tree[100];

struct point{
	int cost;
};

struct edge{
	int from;
	int to;
	int cost;
};

int find(int x){
	if(tree[x] == -1){
		return x;
	}
	else{
		int tmp = find(tree[x]);
		tree[x] = tmp;
		return tmp;
	}
}

bool cmp(edge a,edge b){
	return a.cost < b.cost;
}

int main(){
	int num;
	scanf("%d",&num);
	
	point p[100];
	int Pnum = 0;
	for(int i = 0;i < num;i++){
		scanf("%d",&(p + Pnum)->cost);
		Pnum++;
	}
	
	edge e[1000];
	int Enum = 0;
	int tmp;
	for(int i = 1;i <= num;i++){
		for(int j = 1;j <= num;j++){	
			if(i == j){
				scanf("%d",&tmp);
				continue;
			}
			else if(i > j){
				scanf("%d",&tmp);
				continue;
			}
			scanf("%d",&(e + Enum)->cost);
			(e + Enum)->from = i;
			(e + Enum)->to = j;
			Enum++;
		}
	}
	
	for(int i = 0;i < Pnum;i++){
		(e + Enum)->from = 0;
		(e + Enum)->to = i + 1;
		(e + Enum)->cost = (p + i)->cost;		
		Enum++;		
	}
	 
	sort(e,e + Enum,cmp);
	
	for(int i = 0;i < num + 1;i++){
		tree[i] = -1;
	}
	
	int sum = 0;
	for(int i = 0;i < Enum;i++){
		int a = find((e + i)->from);
		int b = find((e + i)->to);
		if(a != b){
			tree[a] = b;
			sum += (e + i)->cost;
		}
	}
	
	printf("%d\n",sum);
	return 0;
}

杭电2018复试上机真题（第三题更新）

相关推荐