1 条题解

  • 0
    @ 2026-5-5 23:02:38

    删除所有 nn 个节点的最佳方法是按照它们能量值的递减顺序进行删除。

    证明

    考虑每条边 (x,y)(x, y),当它被删除时(即其中一端被移除时),它会贡献 vxv_xvyv_y 到总代价中。

    如果我们按照能量值递减的顺序删除顶点,那么每条边只会在删除能量值较大的那一端时,贡献另一端的能量值(即较小的那个)。因此每条边的贡献为 min(vx,vy)\min(v_x, v_y),总代价达到最低。

    ```cpp
    #include <bits/stdc++.h>
    using namespace std;
    
    int main() {
        int n, m;
        cin >> n >> m;
        vector<int> v(n + 1);
        for (int i = 1; i <= n; ++i) {
            cin >> v[i];
        }
        long long ans = 0;
        for (int i = 0; i < m; ++i) {
            int x, y;
            cin >> x >> y;
            ans += min(v[x], v[y]);
        }
        cout << ans << endl;
        return 0;
    }
    
    • 1

    信息

    ID
    6975
    时间
    1000ms
    内存
    256MiB
    难度
    3
    标签
    递交数
    1
    已通过
    1
    上传者