蓝桥杯 ALGO-6 安慰奶牛

算法训练安慰奶牛

时间限制：1.0s 内存限制：256.0MB

问题描述

Farmer John变得非常懒，他不想再继续维护供奶牛之间供通行的道路。道路被用来连接N个牧场，牧场被连续地编号为1到N。每一个牧场都是一个奶牛的家。FJ计划除去P条道路中尽可能多的道路，但是还要保持牧场之间的连通性。你首先要决定那些道路是需要保留的N-1条道路。第j条双向道路连接了牧场Sj和Ej(1 <= Sj <= N; 1 <= Ej <= N; Sj != Ej)，而且走完它需要Lj的时间。没有两个牧场是被一条以上的道路所连接。奶牛们非常伤心，因为她们的交通系统被削减了。你需要到每一个奶牛的住处去安慰她们。每次你到达第i个牧场的时候(即使你已经到过)，你必须花去Ci的时间和奶牛交谈。你每个晚上都会在同一个牧场(这是供你选择的)过夜，直到奶牛们都从悲伤中缓过神来。在早上起来和晚上回去睡觉的时候，你都需要和在你睡觉的牧场的奶牛交谈一次。这样你才能完成你的交谈任务。假设Farmer John采纳了你的建议，请计算出使所有奶牛都被安慰的最少时间。

输入格式

第1行包含两个整数N和P。

接下来N行，每行包含一个整数Ci。

接下来P行，每行包含三个整数Sj, Ej和Lj。

输出格式

输出一个整数, 所需要的总时间(包含和在你所在的牧场的奶牛的两次谈话时间)。

样例输入

5 7
10
10
20
6
30
1 2 5
2 3 5
2 4 12
3 4 17
2 5 15
3 5 6

样例输出

176

数据规模与约定

5 <= N <= 10000，N-1 <= P <= 100000，0 <= Lj <= 1000，1 <= Ci <= 1,000。

分析：题目的样例有误。第一行输入应为5 6，因为下方只有六行数据。此时输出为178。

题目是求图的最小生成树，但是不能直接使用边权来构造。“你每个晚上都会在同一个牧场(这是供你选择的)过夜”，说明需要寻找一个起始点；“你需要到每一个奶牛的住处去安慰她们。每次你到达第i个牧场的时候(即使你已经到过)，你必须花去Ci的时间和奶牛交谈”，说明所花费时间由点权和边权共同决定。由此可知题目的要求：在图中寻找一起点，遍历整个图并最终回到起点，构造最小生成树使得花费时间最少。

因此可知，直接用边权构造是错误的，因为这种做法会忽略掉点权对结果的影响。

蓝桥杯 ALGO-6 安慰奶牛

如图是选择的一个树的样例，点权与边权标记在图上。假设起点为1号，则整个遍历过程为1->2->3->5->3->2->4->2->1。用w(u, v)表示顶点u, v之间的边权，用c(v)表示顶点v的点权，则整个过程的时间消耗为：c(1) + w(1, 2) + c(2) + w(2, 3) + c(3) + w(3, 5) + c(5) + w(3, 5) + c(3) + w(2, 3) + c(2) + w(2, 4) + c(4) + w(2, 4) + c(2) + w(1, 2) + c(1)。

整理可得：c(1) + [c(1) + 2 * w(1, 2) + c(2)] + [c(2) + 2 * w(2, 3) + c(3)] + [c(3) + 2 * w(3, 5) + c(5)] + [c(2) + 2 * w(2, 4) + c(4)]

可以看出，除了起点会有一次重复外，每一条边都可以与这条边的边权与点权的线性组合产生映射关系，比如(1, 2)这条边对应[c(1) + 2 * w(1, 2) + c(2)]。我们可以将生成树的新边权替换为边权与点权的组合。同时也可以看出，对于同一个生成树，唯一决定总时间的变量是起点的权值。可以取一个点权最小的点作为起点是总时间最少。

综上，最后的答案即为生成树的新边权的和与最小点权的和。

代码：

#include<iostream>
#include<algorithm>
#define MAXN 10001
#define MAXP 100001
using namespace std;
int N, P;
struct Edge {
	int u;
	int v;
	int weight;
}G[MAXP];
int C[MAXN] = { 0 };
int father[MAXN] = { 0 };
bool cmp(Edge e1, Edge e2) {
	return e1.weight < e2.weight;
}
int findFather(int x) {
	int a = x;
	while (x != father[x]) {
		x = father[x];
	}
	while (a != father[a]) {
		int z = a;
		a = father[a];
		father[z] = x;
	}
	return x;
}
int kruskal() {
	int sum = 0;
	int cnt = 0;
	int flag = 1;
	for (int i = 1; i <= N; i++) {
		father[i] = i;
	}
	sort(G, G + P, cmp);
	for (int i = 0; i < P; i++) {
		int u = G[i].u;
		int v = G[i].v;
		int faU = findFather(u);
		int faV = findFather(v);
		if (faU != faV) {
			father[faU] = faV;
			sum += G[i].weight;
			cnt++;
			if (cnt == N - 1) {
				break;
			}
		}
	}
	return sum;
}
int main() {
	cin >> N >> P;
	int minC = 0x3fffffff;
	for (int i = 1; i <= N; i++) {
		cin >> C[i];
		minC = min(C[i], minC);
	}
	for (int i = 0; i < P; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		G[i] = Edge{ u, v, w * 2 + C[u] + C[v] };
	}
	int ans = kruskal() + minC;
	cout << ans << endl;
	return 0;
}

蓝桥杯 ALGO-6 安慰奶牛

相关推荐