第十四届蓝桥杯集训——练习解题阶段(无序阶段)-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个月回忆一下你真正的认真刷过题吗，如果你真的用尽所有的精力去努力了，那么我相信你最终的成绩一定会让你满意的，加油。

第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-6 算法训练安慰奶牛最小生成树