题目描述

你有一张无向图 G={V,E},这张无向图有 n 个点 m 条边组成。
并且这是一张带权图,只有点权。
你想把这个图删干净,它的方法是这样的。每次选择一个点,将它删掉,但删这个点是需要代价的。
假设与这个点相连的还没被删掉的点是 u1,u2,u3,...,uk 。
你将会增加 a[u1]+a[u2]+a[u3]+,..+a[uk] 的疲劳值。
你想将所有点都删掉,并且删完后自己的疲劳值之和最小,你还想求出这个疲劳值。

输入格式

从文件 god.in 中读入数据。
第一行两个数 n,m 表示一张 n 个点 m 条边的图。
第二行 n 个数 ai 表示点权。
接下来 m 行每行两个数 u,v ,表示有一条连接 u,v 的边。
数据保证任意两个点之间最多一条边相连,并且不存在自环。

输出格式

输出到文件 god.out 中。
你需要输出这个最小疲劳值是多少。

输入输出样例

输入 #1

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

输出 #1

40

分析

我们把问题进行转换,仔细观察题意,我们可以发现,原问题可以变为:对于每一条边,连接的两个结点一定要选一个结点,并且加上这个点的疲劳值。我们怎么理解这个转换呢?我们考虑删除了一个点 u ,那么对于每个出边 v ,显然边 (u,v) 只会有点 u 被删除,那么对于任意的点 u ,对于它的每个出边 v ,边 (u,v) 也只会有 u v 一个点被删除,即对于任意的边 (u,v) u,v 只会有一个点被选取,那么就得加上另一个点的疲劳值。故原问题可以转化为 “对于每一条边,连接的两个结点一定要选一个结点,并且加上这个点的疲劳值”。

显然,我们要选的点是疲劳值小的点。 时间复杂度:O(m)

代码

#include <bits/stdc++.h>
using namespace std;
int a[100001], n, m, x, y;
long long ans;
int main() {
    freopen("god.in", "r", stdin);
    freopen("god.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &x, &y);
        ans += min(a[x], a[y]);
    }
    printf("%lld", ans);
    return 0;
}
最后修改:2020 年 09 月 15 日 09 : 08 PM
如果觉得我的文章对你有用,请随意赞赏