[USACO08NOV] Cheering up the Cow G

GitHub跳转原题关系图返回列表

在保留成树的前提下，一条边必走两次，而点 i 的谈话时间会按它在树中的度数计入；把每条边改写成 2*l+c_u+c_v，再额外加上最小的起点费用即可。

OJ: luogu

题目 ID: P2916

难度:普及+/提高

标签:图论最小生成树并查集

日期: 2026-06-20 00:45

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结
  6. 一图流解析

题意

给一张连通无向图，每个点有一个“谈话时间” CiC_i，每条边有一个路程时间 LjL_j。

你要删边，尽量少保留道路，但仍然要让所有点连通。之后选择一个起点出发，走遍所有点至少一次，最后回到起点。每次经过一个点，都要再花一次 CiC_i 的时间说话。

问最小总时间是多少。

思路

先看一个小数据暴力：

cpp
// brute.cpp：枚举所有生成树，再枚举起点，直接按定义比较总时间。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10;
const int MAXM = 30;
const long long INF = (1LL << 60);

struct Edge {
    int u, v, len;
} edges[MAXM];

int n, p;
int cost[MAXN];
int picked[MAXM];
int deg[MAXN];
int fa[MAXN];
long long best_answer;

void init_dsu() {
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
        deg[i] = 0;
    }
}

int find_root(int x) {
    if (fa[x] == x) {
        return x;
    }
    fa[x] = find_root(fa[x]);
    return fa[x];
}

void unite(int x, int y) {
    x = find_root(x);
    y = find_root(y);
    if (x != y) {
        fa[x] = y;
    }
}

void check_tree(int picked_cnt) {
    if (picked_cnt != n - 1) {
        return;
    }

    init_dsu();
    long long road_sum = 0;

    for (int i = 1; i <= picked_cnt; i++) {
        Edge &e = edges[picked[i]];
        road_sum += e.len;
        deg[e.u]++;
        deg[e.v]++;
        unite(e.u, e.v);
    }

    int root = find_root(1);
    for (int i = 2; i <= n; i++) {
        if (find_root(i) != root) {
            return;
        }
    }

    long long talk_sum = 0;
    for (int i = 1; i <= n; i++) {
        talk_sum += 1LL * deg[i] * cost[i];
    }

    for (int start = 1; start <= n; start++) {
        best_answer = min(best_answer, road_sum * 2 + talk_sum + cost[start]);
    }
}

void dfs(int pos, int picked_cnt) {
    if (picked_cnt > n - 1) {
        return;
    }
    if (pos > p) {
        check_tree(picked_cnt);
        return;
    }

    picked[picked_cnt + 1] = pos;
    dfs(pos + 1, picked_cnt + 1);
    dfs(pos + 1, picked_cnt);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> p;
    for (int i = 1; i <= n; i++) {
        cin >> cost[i];
    }
    for (int i = 1; i <= p; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].len;
    }

    best_answer = INF;
    dfs(1, 0);
    cout << best_answer << '\n';

    return 0;
}

暴力做法是：

  1. 枚举所有生成树
  2. 再枚举住在哪个点
  3. 直接按树上的代价公式计算总时间

这个思路能帮助理解，但边多时肯定不行。

先看“删边尽量多，但还要连通”这一句。能保留的最少边数一定是 n−1n-1，所以最后留下来的结构一定是一棵树。

在树上，如果要从某个点出发，走遍所有点，再回到出发点，那么：

  • 每条边都必须走两次
    • 一次进子树
    • 一次从子树回来

所以道路贡献固定是：

2 * 所有保留边长度之和

再看点权贡献。

设最后保留的是一棵树，起点是 r：

  • 非起点 i 会被经过 deg⁡(i)\deg(i) 次
  • 起点 r 会被经过 deg⁡(r)+1\deg(r) + 1 次
    • 多出来的这一次，就是一开始出发前在家里也要谈一次

所以总谈话时间是：

∑(deg⁡(i)⋅Ci)+Cr\sum(\deg(i) \cdot C_i) + C_r

把 ∑(deg⁡(i)⋅Ci)\sum(\deg(i) \cdot C_i) 换个角度看：

  • 树上每条边 (u,v)(u, v)，都会给 deg⁡(u)\deg(u) 和 deg⁡(v)\deg(v) 各贡献一次
  • 所以所有点权项加起来，等价于把每条边贡献成 Cu+CvC_u + C_v

于是整棵树的总代价就是：

Cr+∑(2⋅L(u,v)+Cu+Cv)C_r + \sum(2\cdot L(u,v) + C_u + C_v)

这里 CrC_r 显然应该取全图最小的那个点，因为树一定包含所有点。

剩下的部分就完全变成了最小生成树：

  • 把原边权 LL
  • 改成新边权 2⋅L+Cu+Cv2\cdot L + C_u + C_v

然后在这张新图上跑一遍 MST 即可。

代码

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

const int MAXN = 10005;
const int MAXM = 100005;

struct Edge {
    int u, v;
    int w;

    bool operator<(const Edge &other) const {
        return w < other.w;
    }
} edges[MAXM];

int n, p;
int cost[MAXN];
int fa[MAXN];

void init_dsu(int n) {
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
    }
}

int find_root(int x) {
    if (fa[x] == x) {
        return x;
    }
    fa[x] = find_root(fa[x]);
    return fa[x];
}

bool unite(int x, int y) {
    x = find_root(x);
    y = find_root(y);
    if (x == y) {
        return false;
    }
    fa[x] = y;
    return true;
}

long long kruskal() {
    sort(edges + 1, edges + p + 1);
    init_dsu(n);

    long long answer = 0;
    int used = 0;

    for (int i = 1; i <= p; i++) {
        if (!unite(edges[i].u, edges[i].v)) {
            continue;
        }
        answer += edges[i].w;
        used++;
        if (used == n - 1) {
            break;
        }
    }

    return answer;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> p;

    int min_cost = 1e9;
    for (int i = 1; i <= n; i++) {
        cin >> cost[i];
        min_cost = min(min_cost, cost[i]);
    }

    for (int i = 1; i <= p; i++) {
        int u, v, len;
        cin >> u >> v >> len;
        edges[i] = {u, v, 2 * len + cost[u] + cost[v]};
    }

    cout << kruskal() + min_cost << '\n';

    return 0;
}

复杂度

设点数为 n，边数为 p。

Kruskal 的复杂度是：

  • 排序 O(plogp)O(p log p)
  • 并查集合并 O(pα(n))O(p \alpha(n))

总时间复杂度 O(plogp)O(p log p)，空间复杂度 O(n+p)O(n + p)。

总结

这题难点不在 MST 本身，而在先把“树上闭合走一圈”的总代价拆开。只要看出：

  • 边一定走两次
  • 点权可以按树边两端分摊

就能把原题规整成一棵带新边权的最小生成树。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

一图流解析