完整题面

一、前置知识

• 最小生成树（prim 或 Kruskal）

二、题目描述

Bessie 的 $N$（$2\le N\le 10^5$）个奶牛伙伴（编号为 $1\cdots N$）每一个都拥有自己的农场。对于每个 $1\le i\le N$，伙伴 i 想要访问伙伴 $a_i$（$a_i\ne i$）。

给定 $1\dots N$ 的一个排列 $(p_1,p_2,\dots ,p_N)$，访问按以下方式发生。

对于 $1$ 到 $N$ 的每一个 $i$：

• 如果伙伴 $a_{p_i}$ 已经离开了她的农场，则伙伴 $p_i$ 仍然留在她的农场。
• 否则，伙伴 $p_i$ 离开她的农场去访问伙伴 $a_{p_i}$ 的农场。这次访问会产生快乐的哞叫 $v_{p_i}$ 次（$0\le v_{p_i}\le 10^9$）。

对于所有可能的排列 $p$，计算所有访问结束后可能得到的最大哞叫次数。

三、思考题目

我们可以把 奶牛访问 的关系转换为 每个点出度为 $1$ 的一张图

我们希望在图上 删去一些边，将图转换为 DAG图，再结合 每个点出度为 $1$ 的一张图，可以得到这是一颗 树，也就是要求 生成树 的边长之和

需要求最大叫声次数，所以就是求 最大生成树 的边长之和

有了思路，代码就很简单了

四、完整代码

#include <cstdio>
#include <algorithm>
using namespace std;

int n;
struct Edge { int u, v, w; } e[100005];
bool cmp(Edge x, Edge y) {
    return x.w > y.w;
}

int f[100005];
int find(int x) {
    if (f[x] != x) f[x] = find(f[x]);
    return f[x];
}
void merge(int x, int y) {
    f[find(x)] = find(y);
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        e[i].u = i;
        scanf("%d%d", &e[i].v, &e[i].w);
    }
    sort(e + 1, e + n + 1, cmp);
    
    for (int i = 1; i <= n; i++)
        f[i] = i;
    long long ans = 0;
    for (int i = 1; i <= n; i++)
        if (find(e[i].u) != find(e[i].v)) {
            ans += e[i].w;
            merge(e[i].u, e[i].v);
        }
    printf("%lld\n", ans);
    return 0;
}

提交看看

五、代码优化

1. 快速输入函数

2. 按秩合并优化并查集

3. 提前终止循环：在已选择 $n-1$ 条边后提前跳出循环，减少不必要的遍历，优化运行时间。

4. 结构体排序优化：使用 const 引用传参的 cmp 函数，略微提升比较效率。

5. 添加注释

6. 修改变量名

#include <cstdio>
#include <algorithm>
using namespace std;

// 快速输入函数，用于加速输入
inline int read() {
    int x = 0, c = getchar();
    while (c < '0' || c > '9') c = getchar(); // 跳过非数字字符
    while (c >= '0' && c <= '9') {
        x = x * 10 + c - '0'; // 计算数字
        c = getchar();
    }
    return x;
}

const int MAX_EDGES = 100005; // 最大边数

int n; // 顶点数
struct Edge {
    int u, v, w; // 边的起点、终点和权重
} edges[MAX_EDGES];

// 比较函数，按边的权重从大到小排序
bool compareEdges(const Edge& a, const Edge& b) {
    return a.w > b.w;
}

int parent[MAX_EDGES], rk[MAX_EDGES]; // 并查集的父节点和秩数组

// 查找函数，带路径压缩
int find(int x) {
    return parent[x] == x ? x : (parent[x] = find(parent[x]));
}

// 合并函数，带按秩合并优化
void merge(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return; // 如果已经在同一个集合，直接返回
    if (rk[x] < rk[y]) parent[x] = y; // 将秩较小的树合并到秩较大的树
    else {
        parent[y] = x;
        if (rk[x] == rk[y]) rk[x]++; // 如果秩相等，增加秩
    }
}

int main() {
    n = read(); // 读取顶点数
    for (int i = 1; i <= n; ++i) {
        edges[i].u = i; // 起点为当前顶点
        edges[i].v = read(); // 读取终点
        edges[i].w = read(); // 读取权重
    }
    // 按边的权重从大到小排序
    sort(edges + 1, edges + n + 1, compareEdges);

    // 初始化并查集
    for (int i = 1; i <= n; ++i) {
        parent[i] = i; // 每个顶点初始时是自己的父节点
        rk[i] = 1;   // 初始秩为1
    }

    long long totalWeight = 0; // 最大生成树的总权重
    int selectedEdges = 0;     // 已选边的数量
    for (int i = 1; i <= n && selectedEdges < n - 1; ++i) {
        int u = edges[i].u, v = edges[i].v;
        if (find(u) != find(v)) { // 如果边的两个顶点不在同一个集合
            totalWeight += edges[i].w; // 将边的权重加入总权重
            merge(u, v);               // 合并两个集合
            selectedEdges++;           // 已选边数加1
        }
    }
    printf("%lld\n", totalWeight); // 输出最大生成树的总权重
    return 0;
}

建议、代码来源：deepseek（已验证代码正确性）

就好了