洛谷 P7528 分析（别看）

科技起源的小号1

2026-08-27 12:42:17

发布于：天津

3阅读

0回复

0点赞

原题链接

1 题目

1.1 题目所需求出内容

对于本题，最终要求：一个最小值

1.2 题目背景、允许、禁止与限制

背景：
有 $n$ 个点 $2n$ 组传送门
每个点有 $4$ 个传送门编号
你现在所在位置表示为 $(所在节点,所在传送门)$
每个点内部的前两个传送门编号在一组，后两个传送门编号在一组（但大概率并不是同样的编号）
允许：
你可以有两种操作使自己移动：

从当前点传送门编号传送到另一个传送门编号所在的点（但是传送过去后你的位置是后者的位置）
移动到同组的另外一个传送门

设当前点为 $i$ ，花费 $c_i$ 重新改变传送门顺序，打乱完后的传送门前两个为一组，后两个为一组

求让所有全部 (点，传送门) 状态互相可达的最小花费

1.3 题目数据范围与猜测

$2 \le n \le 10^5 \longrightarrow O(n~log~n)$

1.4 一句话概括题意

通过改变传送门的顺序使得在特定移动条件下所有状态合并成一个大环
这个大环是整个题目的关键，我们最终就要让其成为大环

2 题目破题推导

2.1 第一步：建模

可以把传送门看成图上的点，把传送门之间的配对看成图上的边

2.2 第二步：分情况讨论

一开始就成大环的情况（部分）
如何判断？
当然就是将所有传送门编号按照一开始的规则连接在一起
那如何将一组相同的传送门编号连接在一起呢？不需要考虑，因为连接传送门编号的时候相当于把所有为这个编号的传送门都自动连接在一起了
那些连接在一起的传送门就不需要考虑了，因为他们已经可以到达了
一开始并没有成大环的情况（另外一部分）
题目中有一个关键的“交换”操作
考虑交换为两个不同环带来的影响：

发现可以将两个环合并成一个
这样不就更接近“大环”的要求了吗

3 模型匹配

环形连接：并查集（天然实现，合并的是传送门编号，开始的时候合并的就是每组的前两个和后两个，因为他们本身就是连接起来的，哪怕不在同一个点也没问题），相当于实现连通块问题
贪心选择交换点：使用类似kruskal的思想，因为如果有 $k$ 个连通块，只需要 $k-1$ 次就可以合并完成，那么按照交换所需代价从小到大排序，最终可以得到一个整体大环

4 最终代码（禁止抄袭，仅用于参考）

/*
如何判断初始是否全连通？
    把1...n每个点的前两个传送门合并，后两个传送门合并
    若只有一个集合，则初始全连通
若有多个集合，将这些集合合并为一个
    因为交换两个集合中的两个点交换就可以合并
    因此若点i前两个传送门与后两个传送门不在一个集合里，可以花费c_v_i将其交换（将两个集合合并）
    那最小花费是多少？类似Kruskal，先合并较小的花费，再合并较大的花费
*/
#include <bits/stdc++.h>
using namespace std;

int n;
const int N = (1e5 + 10) * 2;
struct node{
    int c;
    int p1, p2, p3, p4;
}a[N];
bool cmp(node x, node y){
    return x.c < y.c;
}
int fa[N];
bool vis[N];
void init(){
    for (int i = 1;i <= 2 * n;i++){
        fa[i] = i;
        vis[i] = false;
    }
}
int get(int x){
    if (fa[x] != x){
        fa[x] = get(fa[x]);
    }
    return fa[x];
}
void merge(int x, int y){
    x = get(x);
    y = get(y);
    if (x != y){
        fa[x] = y;
    }
}

int main(){

    cin >> n;
    init();
    for (int i = 1;i <= n;i++){
        cin >> a[i].c;
        cin >> a[i].p1 >> a[i].p2 >> a[i].p3 >> a[i].p4;
        int p1r = get(a[i].p1);
        int p2r = get(a[i].p2);
        int p3r = get(a[i].p3);
        int p4r = get(a[i].p4);
        merge(p1r, p2r);
        merge(p3r, p4r);
    }
    sort(a + 1, a + 1 + n, cmp);
    int cnt = 0;
    int ans = 0;
    for (int i = 1;i <= 2 * n;i++){
        if (vis[get(i)] == false){
            cnt++;
            vis[get(i)] == true;
        }
    }
    for (int i = 1;i <= n;i++){
        if (cnt == 1){
            cout << ans;
            return 0;
        }
        int p1r = get(a[i].p1);
        int p3r = get(a[i].p3);
        if (p1r != p3r){
            fa[p1r] = p3r;
            cnt--;
            ans += a[i].c;
        }
    }
    cout << ans;
    
    return 0;
}