P7528 题解

· · 题解

本蒟蒻看到各位大佬的代码都这么的高端大气，那么就由我来一发朴实无华的题解来弥补你谷的空缺吧。

【朴实无华的分析】

十分显然的 一道 Kruskal 最小生成树题。

题意还是比较容易读懂的，主要就是关于题意转换比较难想，让我们看一下具体操作，究竟发生了些什么。

如以下问题所述：存在两个节点 pi ， 每个节点有 v_1, v_2, v_3, v_4 四个传送门， 两个节点的关系如下图。

那么很显然， 你可以从 p_1v_1 进入到达 p_2v_1, p_2v_2 这两个位置, 但是你无法到达 p_2 的另外两个位置。

那么怎么办呢？

没错，就是通过改变传送门的位置从而使所有的位置组成一个连通块。很显然图中存在两个环， 我们需要将它变成一个环，那么就可以达到目的了。

操作完之后大概是这个样子：

这样你就会发现，你可以从任意位置出发，到达给定的任意位置，那么我们就达到了目的。

具体实现请看代码 ------------------->

【朴实无华的Code】

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1e6 + 5;//数据范围1e6足矣 

int n;
int d, ans;
int f[N>>1];//我们把传送门抽象成点，所以f数组要开2*N 
int p[N][4];//用于存四个传送门的信息 

struct bal {
    int pos;
    int sum;
};
bal t[N];//结构体存点的信息 

int re() {//快读不赘述 
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0'||ch > '9') {
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while (ch <= '9'&&ch >= '0') {
        x = x*10+ch-'0';
        ch = getchar();
    }
    return x*f;
}

int find(int x) {//这里提一下，优化后的找父亲 
    while(x != f[x])
    x = f[x] = f[f[x]];//路径压缩与找父亲同步，比递归省时 
    return x;
}

void un(int a, int b) {//合并 
    a = find(a);
    b = find(b);
    f[a] = b;
}

int cmp(bal a, bal b) {//按牟尼数进行排序 
    return a.sum < b.sum;
}

signed main() {
    n = re();
    for(int i = 1; i <= n<<1; i++)//注意要n<<1 
        f[i] = i;
    for(int i = 1; i <= n; i++) {
        t[i].pos = i; t[i].sum = re();
        p[i][0] = re(); p[i][1] = re();
        p[i][2] = re(); p[i][3] = re();
        un(p[i][0], p[i][1]);
        un(p[i][2], p[i][3]);//将已经联通的合并，初始化为多个环
    }
    sort(t + 1, t + n + 1, cmp);//cmp
    for(int i = 1; i <= n; i++) {//经典Kruskal，使所有环联通
        d = t[i].pos;
        int x = find(p[d][0]);
        int y = find(p[d][2]);
        if(x != y) {
            f[y] = x;
            ans += t[i].sum;
        }//这里直接跑完n即可，因为我不会优化... 
    }
    printf("%d\n", ans); 
    return 0;//好习惯哦 
}

END

其他一些无关紧要的东西

欢迎大佬们光顾我的博客