第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-6 算法训练 安慰奶牛 最小生成树
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-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%数据。
第六届Java国赛C组 | https://laoshifu.blog.csdn.net/article/details/123440705 |
---|---|
第七届Java国赛C组 | https://laoshifu.blog.csdn.net/article/details/123442982 |
第八届Java国赛C组 | https://laoshifu.blog.csdn.net/article/details/123443626 |
第九届Java国赛C组 | https://laoshifu.blog.csdn.net/article/details/123443908 |
第十届Java国赛C组 | https://laoshifu.blog.csdn.net/article/details/123444946 |
第十一届Java国赛C组 | https://laoshifu.blog.csdn.net/article/details/123445601 |
第十二届Java国赛C组 | https://laoshifu.blog.csdn.net/article/details/123446589 |
相关文章
- 【NLP基础】英文关键词抽取RAKE算法
- ECCV 2022 | CMU提出首个快速知识蒸馏的视觉框架:ResNet50 80.1%精度,训练加速30%
- 南理工&上海AI Lab提出Uniform Masking,为基于金字塔结构的视觉Transformer进行MAE预训练!
- opencv 人脸识别 (二)训练和识别
- 【Kaggle竞赛】迭代训练模型
- 完成OpenCV分类器训练的最简单方法
- Pytorch模型训练实用教程学习笔记:四、优化器与学习率调整
- 用训练好的生成对抗网络生成和挑选图片
- 蓝桥杯 算法训练 3000米排名预测---------C语言—菜鸟级
- 蓝桥杯算法训练 最大体积 (gcd+完全背包)------C语言—菜鸟级
- Python statsmodel包训练LR模型
- 多模态再次统一!Meta发布自监督算法data2vec 2.0:训练效率最高提升16倍!
- [BIB | 论文简读] BioGPT:用于生物医学文本生成和挖掘的生成性预训练转化器
- DN-DETR:引入去噪训练以加速收敛
- 再掀强化学习变革!DeepMind提出「算法蒸馏」:可探索的预训练强化学习Transformer
- 第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1 算法训练 区间k大数查询
- 第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-3 算法训练 K好数
- 第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-4 算法训练 结点选择
- 第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-49 算法训练 寻找数组中最大值
- 【数据挖掘】分类任务简介 ( 分类概念 | 分类和预测 | 分类过程 | 训练集 | 测试集 | 数据预处理 | 有监督学习 )
- 在 PyTorch 中使用梯度检查点在GPU 上训练更大的模型
- 细思恐极!PimEyes竟盗用死人照片来训练面部识别算法
- 「人工智能训练师」国家职业技能标准发布:共有五大级别,你是第几级?
- gensim 中文语料训练 word2vec详解大数据
- 只训练一次数据就能识别出物体,谷歌全新 AI 算法“单次学习”
- 中国跳水队用上3D+AI训练系统 百度打造
- 现场|David Silver原文演讲:揭秘新版AlphaGo算法和训练细节