CCF CSP 数据中心（专用）

整数浮点

于 2019-08-16 16:44:21 发布

阅读量354

点赞数

分类专栏：升级

本文为博主原创文章，未经博主允许不得以任何形式转载！欢迎访问整数浮点www.wangliguang.cn

本文链接：https://blog.csdn.net/happywlg123/article/details/99681290

版权

该博客主要探讨了如何解决数据中心问题，实际上是一个最小生成树问题。作者通过分析样例，提出不需要考虑根节点位置，只需找到最小生成树即可满足要求。博客提供了三种不同的实现代码，包括写cmp函数和重载<运算符的两种不使用容器的方法，以及一种使用容器的方法。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目

试题编号： 201812-4
试题名称：数据中心
时间限制： 1.0s
内存限制： 512.0MB
问题描述：
在这里插入图片描述

样例输入

4
5
1
1 2 3
1 3 4
1 4 5
2 3 8
3 4 2

样例输出

样例说明

下图是样例说明。
在这里插入图片描述

分析

虽然题目说的很复杂，但是仔细观察样例后发现，其实就是一个最小生成树的问题，甚至都不需要考虑根节点在什么位置，因为无论在什么位置，只要把最小生成树求出来，问题就是符合题目要求的。

代码

代码1：写cmp函数，不使用容器

#include <bits/stdc++.h>
using namespace std;

#define MAX 100001
#define MAXN 500001

struct Edge{
   
    int u;
    int v;
    int w;
    Edge(){
   };
    Edge(int u1, int v1, int w1):u(u1), v(v1), w(w1){
   }
};

int pre[MAXN];
Edge edge[MAX];

bool cmp(Edge e1, Edge e2){
   
    return e1.w < e2.w;
}

int find(int root){
   
    int tmp, son;
    son = root;
    while(root != pre[root]){
   
        root = pre[root];
    }
    while(son != root){
   
        tmp = pre[son];
        pre[son] = root;
        son = root;
    }
    return root;
}

bool join(int x, int y){
   
    int rootx = find(x);
    int rooty = find(y);
    if(rootx != rooty){
   
        pre[rootx] = rooty;
        return true;
    }
    return false;
}

int main(

最低0.47元/天解锁文章