第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-6 算法训练 安慰奶牛 最小生成树
【摘要】 第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-6 算法训练 安慰奶牛 最小生成树
前言
算法训练 安慰奶牛 最小生成树
C++语言
Java语言
Python语言
总结
第六届——第十三届省赛题解
第六届——第十二届省赛题解
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-6 算法训练 安慰奶牛 最小生成树
目录
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-6 算法训练 安慰奶牛 最小生成树
前言
最近的一些文章都可能会很碎，写到哪里是哪里，过一阵子会具体的整理一遍，这里其它的类型题先往后排一排，因为蓝桥最后考的也就是对题目逻辑的理解能力，也就是dp分析能力了，所以就主要目标定在这里，最近的题目会很散，很多，基本上都是网罗全网的一些dp练习题进行二次训练，准备比赛的学生底子薄的先不建议看啊，当然，脑子快的例外，可以直接跳过之前的一切直接来看即可，只需要你在高中的时候数学成绩还可以那就没啥问题，其实，dp就是规律总结，我们只需要推导出对应题目的数学规律就可以直接操作，可能是一维数组，也可能是二维数组，总体来看二维数组的较多，但是如果能降为的话建议降为，因为如果降为起来你看看时间复杂度就知道咋回事了，那么在这里祝大家能无序的各种看明白，争取能帮助到大家。
算法训练 安慰奶牛 最小生成树
资源限制
内存限制：256.0MB C/C++时间限制：1.0s Java时间限制：3.0s Python时间限制：5.0s
问题描述
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 6
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
题解：
# include <stdio.h>
# include <stdlib.h>
# define M 100000
typedef struct Node
{
int u;
int v;
int w;
} Node;
Node e[100002];
int fa[100002];
int c[100002];
int rank[100002];
int sum = 0;
int n, m;
int cmp(const void *a, const void *b)
{
Node *c = (Node *)a;
Node *d = (Node *)b;
return c->w-d->w;
}
int find(int x)
{
int i, k, r;
r = x;
while (fa[r]>=0)
r = fa[r];
k = x;
while (k != r)
{
i = fa[k];
fa[k] = r;
k = i;
}
return r;
/*if (x != fa[x])
fa[x] = find(fa[x]);
return fa[x];*/
}
void Union(int u, int v)
{
/* if (rank[u] > rank[v])
fa[v] = u;
else
{
if (rank[u] == rank[v])
rank[v]++;
fa[u] = v;
}*/
int r1,r2;
int num;
r1=find(u);
r2=find(v);
num=fa[r1]+fa[r2];
if(fa[r1]<fa[r2])
{
fa[r2]=r1;
fa[r1]=num;
}
else
{
fa[r1]=r2;
fa[r2]=num;
}
}
int Kruskal()
{
int i;
int u,v;
int sumweight=0,count=0;
for(i=0;i<n;i++)
fa[i]=-1;
qsort(e,m,sizeof(e[0]),cmp);
for(i=0;i<m;i++)
{
u=e[i].u;
v=e[i].v;
if(find(u)!=find(v))
{
sumweight+=e[i].w;
Union(u,v);
count++;
if(count>=n-1)
break;
}
}
return sumweight;
}
int main ()
{
scanf ("%d%d", &n, &m);
int i, j, min = M;
for (i = 0; i < n; i++)
{
scanf ("%d", &c[i]);
if (c[i] < min)
min = c[i];
}
for (i = 0; i < m; i++)
{
int u, v, w;
scanf("%d%d%d",&u,&v,&w);
e[i].u=u-1;
e[i].v=v-1;
e[i].w=w*2+c[u-1]+c[v-1];
}
printf ("%d\n", min+Kruskal());
return 0;
}
C++语言
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<iostream>
#include<algorithm>
using namespace std;
const int INF=999999999;
struct wjj
{
int x,y,w;
}edge[100005];
int v[10005],N,P,father[10005],Min=INF;
int _getfather(int x)
{
if(x!=father[x]) father[x]=_getfather(father[x]);
return father[x];
}
void _in(int &x)
{
char t=getchar();
while(t<'0'||'9'<t) t=getchar();
for(x=t-'0',t=getchar();'0'<=t&&t<='9';x=x*10+t-'0',t=getchar());
}
void _init()
{
_in(N);_in(P);
for(int i=1;i<=N;i++)
{
father[i]=i;
_in(v[i]);
Min=min(Min,v[i]);
}
for(int i=1;i<=P;i++)
{
_in(edge[i].x);_in(edge[i].y);_in(edge[i].w);
edge[i].w<<=1;
edge[i].w+=v[edge[i].x]+v[edge[i].y]; //重新计算边的权值！！！
}
}
void _qst_w(int l,int r)
{
int i=l,j=r,mw=edge[(i+j)>>1].w;
while(i<=j)
{
while(edge[i].w<mw) i++;
while(edge[j].w>mw) j--;
if(i<=j)
{
swap(edge[i],edge[j]);
i++;j--;
}
}
if(l<j) _qst_w(l,j);
if(i<r) _qst_w(i,r);
}
void _solve()//Kruskal
{
_qst_w(1,P);
int fx,fy,k,cnt,tot;
k=cnt=tot=0;
while(cnt<N-1)
{
k++;
fx=_getfather(edge[k].x);
fy=_getfather(edge[k].y);
if(fx!=fy)
{
father[fx]=fy;
tot+=edge[k].w;
cnt++;
}
}
printf("%d\n",tot+Min); //不要忘记最后加上起点的权值（点的最小权值）
}
int main()
{
_init();
_solve();
return 0;
}Java语言
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
public class Main {
class edge {
public int a;
public int b;
public int value;
edge(int a, int b, int value) {
this.a = a;
this.b = b;
this.value = value;
}
}
public void edgeSort(edge[] A){
if(A.length > 1) {
edge[] leftA = getHalfEdge(A, 0);
edge[] rightA = getHalfEdge(A, 1);
edgeSort(leftA);
edgeSort(rightA);
mergeEdgeArray(A, leftA, rightA);
}
}
public edge[] getHalfEdge(edge[] A, int judge) {
edge[] half;
if(judge == 0) {
half = new edge[A.length / 2];
for(int i = 0;i < A.length / 2;i++)
half[i] = A[i];
} else {
half = new edge[A.length - A.length / 2];
for(int i = 0;i < A.length - A.length / 2;i++)
half[i] = A[A.length / 2 + i];
}
return half;
}
public void mergeEdgeArray(edge[] A, edge[] leftA, edge[] rightA) {
int i = 0;
int j = 0;
int len = 0;
while(i < leftA.length && j < rightA.length) {
if(leftA[i].value < rightA[j].value) {
A[len++] = leftA[i++];
} else {
A[len++] = rightA[j++];
}
}
while(i < leftA.length) A[len++] = leftA[i++];
while(j < rightA.length) A[len++] = rightA[j++];
}
//获取节点a的根节点
public int find(int[] id, int a) {
int x, r, k;
r = a;
while(id[r] >= 0) r = id[r];
k = a;
while(k != r) {
x = id[k];
id[k] = r;
k = x;
}
return r;
}
//合并a节点所在树和b节点所在树
public void union(int[] id, int a, int b) {
int ida = find(id, a);
int idb = find(id, b);
int num = id[ida] + id[idb];
if(id[ida] < id[idb]) {
id[idb] = ida;
id[ida] = num;
} else {
id[ida] = idb;
id[idb] = num;
}
}
//获取题意最终结果
public void getMinSpanTree(edge[] A, int[] valueN) {
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
int sum = 0;
int[] id = new int[valueN.length];
for(int i = 0;i < valueN.length;i++)
id[i] = -1;
edgeSort(A);
int count = 0;
for(int i = 0;i < A.length;i++) {
int a = A[i].a;
int b = A[i].b;
int ida = find(id, a - 1);
int idb = find(id, b - 1);
if(ida != idb) {
sum += A[i].value;
count++;
union(id, a - 1, b - 1);
}
if(count >= valueN.length - 1)
break;
}
int minValueN = valueN[0];
for(int i = 0;i < valueN.length;i++) {
if(minValueN > valueN[i]) {
minValueN = valueN[i];
}
}
sum += minValueN;
out.println(sum);
// System.out.println(sum);
out.flush();
}
public static void main(String[] args)throws IOException{
Main test = new Main();
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
// PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
in.nextToken(); int n = (int) in.nval;
in.nextToken(); int p = (int) in.nval;
if(n > 10000 || n < 5)
return;
if(p > 100000 || p < n - 1)
return;
int[] valueN = new int[n];
for(int i = 0;i < n;i++)
{ in.nextToken(); valueN[i] = (int) in.nval;}
edge[] A = new edge[p];
for(int i = 0;i < p;i++) {
in.nextToken(); int a = (int) in.nval;
in.nextToken(); int b = (int) in.nval;
in.nextToken(); int value = (int) in.nval * 2 + valueN[a - 1] + valueN[b - 1];
A[i] = test.new edge(a, b, value);
}
test.getMinSpanTree(A, valueN);
// out.flush();
}
}
Python语言
import math
from collections import deque
from queue import PriorityQueue
from heapq import *
import sys
import operator
n, p = map(int, sys.stdin.readline().split())
val = [0]
f = [i for i in range(n + 1)]
def find(x:int)->int:
if x == f[x]:
return x
else:
f[x] = find(f[x])
return f[x]
edges = []
for i in range(n):
val.append(int(input()))
min_val = min(val[1:])
for i in range(p):
u, v, w = map(int, sys.stdin.readline().split())
w += w + val[u] + val[v]
edges.append((u, v, w))
edges.sort(key=lambda x:x[2])
tot, res = 0, 0
for i in range(p):
u, v = edges[i][0], edges[i][1]
fu, fv = find(u), find(v)
if fu != fv:
tot += 1
res += edges[i][2]
f[fu] = fv
if tot == n - 1:
break
if tot != n - 1:
print("no")
else:
res += min_val
print(res)
总结
这种题幸好大专生不考，如果考大专的孩子们估计能答出来的就很少了，读题解题都挺麻烦的。
没有什么不付出就能拿到的结果，我们都是在负重前行，最终结果与自身先天的脑力有一定的关系，但是还是有很大一部分看自己后天的努力，其实从报名到比赛也就5个月左右，真正刷题的事件也就2个月，2个月回忆一下你真正的认真刷过题吗，如果你真的用尽所有的精力去努力了，那么我相信你最终的成绩一定会让你满意的，加油。
第六届——第十三届省赛题解
所有的题目都做了讲解，最难的有配套的视频，视频提供者是【2020级的弓家宜】先生。
| 第六届Java省赛C组 | https://laoshifu.blog.csdn.net/article/details/123284163 |
| 第七届Java省赛C组 | https://laoshifu.blog.csdn.net/article/details/123285783 |
| 第八届Java省赛C组 | https://laoshifu.blog.csdn.net/article/details/123302677 |
| 第九届Java省赛C组 | https://laoshifu.blog.csdn.net/article/details/123303285 |
| 第十届Java省赛C组 | https://laoshifu.blog.csdn.net/article/details/123319090 |
| 第十一届Java省赛C组 | https://laoshifu.blog.csdn.net/article/details/123320205 |
| 第十二届Java省赛C组第一套 | https://laoshifu.blog.csdn.net/article/details/123413141 |
| 第十二届Java省赛C组第二套 | https://laoshifu.blog.csdn.net/article/details/123413271 |
| 第十三届Java省赛C组 | https://laoshifu.blog.csdn.net/article/details/128891276 |
第六届——第十二届省赛题解
所有题目均有题解，部分第10题非最优解，至少跑20%数据。
【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）