题目描述

难度分:$1400$

输入$n(1 \leq n \leq 1000)$，$m(0 \leq m \leq 2000)$，表示一个$n$点$m$边的无向图。节点编号从$1$开始。保证图中无自环和重边。

然后输入$n$个数，表示每个节点的点权，元素范围$[0,10^5]$。

然后输入$m$条边，每条边输入$x$、$y$，表示有一条无向边连接$x$和$y$。

你需要一个一个地删除这$n$个节点。删除点$v$时，把$v$的所有未删除的邻居的点权之和加入答案。输出答案的最小值。

输入样例$1$

4 3
10 20 30 40
1 4
1 2
2 3

输出样例$1$

40

输入样例$2$

4 4
100 100 100 100
1 2
2 3
2 4
3 4

输出样例$2$

400

输入样例$3$

7 10
40 10 20 10 20 80 40
1 5
4 7
4 5
5 2
5 7
6 4
1 6
1 3
4 3
1 4

输出样例$3$

160

算法

贪心

感觉上就是确定一个删除顺序然后模拟，构建一个数组$w$，$w[u]$表示节点$u$此时相邻节点的权重之和。

直觉上感觉应该就是先把大权重的节点删掉，这样一来可以让后续的节点在删除时代价尽可能低。因此，把所有节点按照点权降序排列然后模拟删点就可以了，在删除节点$u$后，记得把它所有邻居$v$的$w[u]$减少$a[v]$，维护好$w$数组。

复杂度分析

时间复杂度

对所有节点$i$按照自身权重$a[i]$降序排列，时间复杂度为$O(nlog_2n)$。然后模拟删点，每个节点会被删除一次，因此时间复杂度为$O(n+m)$，就是遍历所有节点和边的时间复杂度。

空间复杂度

$a$是题目输入的数组不计入空间，$w$数组的空间是线性的$O(n)$，图的邻接表空间是$O(n+m)$。因此，整个算法的额外空间复杂度为$O(n+m)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 1010;
int n, m, a[N], w[N];
vector<int> graph[N];

int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        graph[i].clear();
        w[i] = 0;
    }
    for(int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        graph[u].push_back(v);
        graph[v].push_back(u);
        w[u] += a[v];
        w[v] += a[u];
    }
    vector<array<int, 2>> tup;
    for(int i = 1; i <= n; i++) {
        tup.push_back({-a[i], i});
    }
    sort(tup.begin(), tup.end());
    long long ans = 0;
    for(int i = 0; i < tup.size(); i++) {
        int u = tup[i][1], cost = w[u];
        ans += cost;
        for(int v: graph[u]) {
            w[v] -= a[u];
        }
    }
    printf("%lld\n", ans);
    return 0;
}