当前位置：首页 > article >正文

洛谷题目 P5994 [PA 2014] Kuglarz 题解（本题较难）

article 2025/1/30 13:55:39

题目传送门：

P5994 [PA 2014] Kuglarz - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

前言：

本题涉及到最小生成树中的 kruskal 算法和并查集算法，图论基础概念两大知识点，瞎按对莱索没有学过图论的或最小生成树的可能会对这道题无从下手，学过最小生成树和图论的初学者对这道题可以说是非常好的历练。难度可以给到中等偏上（~~很简单的呀~~）。

#题目核心目标：

这道题的很新目标是确定最少花费，从而保证能猜出哪些被子底下藏着球，而解题的关键在于将问题转化成最小生成树问题。本题将详细境界。

##问题分析转化：

1、信息关联与节点表示：

把每个被子看做图中的一个节点。对于一个被子序列，我们要确定每个被子是否藏球，而通过魔术师提供的关于区间 $[i,j]$ 内藏球总数奇偶性的信息，就可以逐步推断出每个被子的情况。

例如，知道区间 $[l,r]$ 的询问都对应途中的一条边，变得两个端点分别是 $i-1$ 和 $j$ ,变得权值就是这次询问的花费 $c_{i_{j}}$ 。因为我们可以利用这个区间的奇偶性信息来连接这两个端点所代表的节点状态。

3、问题等价性：

我们的目标使用最少的花费来获取足够的信息来确定所有杯子里是否藏球，这就相当于在图中找到一个变得集合，使得这些边能够连接所有节点，并且这些边的权值总和最小，恰好就是我们经典的最小生成树问题。

###最小生成树选择-Kruskal 算法：

1、具体步骤：

1.1、边的排序：将所有表示询问的边按照花费从小到大进行排序。这里做的目的是优先选择花费晓得询问，以满足最小花费的要求。

1.2、并查集的使用：

并查集是一种用于处理不相交集合合并与查询问题的数据结构。在本题中，我们使用并查集来判断加入一条边后是否会形成环。
初始时，每个节点的父节点就是它自身，表示每个节点都属于一个独立的集合。
对于每条边，我们查找其两个端点所在集合的根节点。如果两个端点的根节点不同，说明这两个端点属于不同的集合，加入这条边不会形成环，我们就将这条边加入到最小生成树中，并合并这两个集合（即将一个集合的根节点指向另一个集合的根节点）。
如果两个端点的根节点相同，说明这两个端点已经在同一个集合中，加入这条边会形成环，我们就跳过这条边。

####代码：

#include <bits/stdc++.h>
using namespace std;
const int M = 2005;
struct E {
    int u, v, w;
    E(int u, int v, int w) : u(u), v(v), w(w) {}
    bool operator<(const E& t) const {
        return w < t.w;
    }
};
int p[M];
int find(int x) {
    if (p[x] != x) {
        p[x] = find(p[x]);
    }
    return p[x];
}
void un(int x, int y) {
    int rx = find(x);
    int ry = find(y);
    if (rx != ry) {
        p[rx] = ry;
    }
}

int main() {
    int n;
    cin >> n;
    vector<E> e;
    for (int i = 1; i <= n; ++i) {
        for (int j = i; j <= n; ++j) {
            int o;
            cin >> o;
            e.emplace_back(i - 1, j, o);
        }
    }
    for (int i = 0; i <= n; ++i) {
        p[i] = i;
    }
    sort(e.begin(), e.end());

    long long C = 0;
    for (const auto& g : e) {
        int u = g.u;
        int v = g.v;
        int w = g.w;
        int ru = find(u); 
        int ry = find(v);
        if (ru != ry) {
            un(u, v);
            C += w;
        }
    }

    cout << C << endl;

    return 0;
}

查看全文

http://www.kler.cn/a/522727.html