蓝桥杯训练 安慰奶牛 (Kruskal MST)

本文主要是介绍蓝桥杯训练 安慰奶牛 (Kruskal MST)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

   
问题描述

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。

题目链接：http://lx.lanqiao.org/problem.page?gpid=T16

题目分析：题意雷死人了，这个人每天要回到预设起点，也就是说对于除了起点以外的每个点都要遍历它们邻接边个数次，则我们可以将每个点的权值设定为边长*2+边两端点的点权，一开始在起点则起点多谈话一次，因为对于同一棵生成树除了起点外的所有将要遍历的点权边权和是个固定的值，因此只需要取点权最小的点做起点，直接求最小生成树

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int const INF = 0x3fffffff;
int const MAXN = 1e4 + 5;
int const MAXM = 1e5 + 5;
int fa[MAXN];
int a[MAXN];
int n, m, ans;struct EDGE
{int x, y;int val;
}e[MAXM];bool cmp(EDGE a, EDGE b)
{return a.val < b.val;
}void UF_set()
{for(int i = 0; i < MAXN; i++)fa[i] = i;
}int Find(int x)
{return x == fa[x] ? x : fa[x] = Find(fa[x]);
}void Union(int a, int b)
{int r1 = Find(a);int r2 = Find(b);if(r1 != r2)fa[r2] = r1;
}void Kruskal()
{UF_set();int cnt = 0;for(int i = 0; i < m; i++){int x = e[i].x;int y = e[i].y;if(Find(x) != Find(y)){Union(x, y);ans += e[i].val;cnt ++;}if(cnt >= n)break;}
}int main()
{ans = 0;int mi = INF;scanf("%d %d", &n, &m);for(int i = 0; i < n; i++){scanf("%d", &a[i]);mi = min(mi, a[i]);}for(int i = 0; i < m; i++){scanf("%d %d %d", &e[i].x, &e[i].y, &e[i].val);e[i].val = e[i].val * 2 + a[e[i].x - 1] + a[e[i].y - 1];}sort(e, e + m, cmp);Kruskal();printf("%d\n", ans + mi);
}

这篇关于蓝桥杯训练 安慰奶牛 (Kruskal MST)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---