题目描述

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

输入格式

从文件 $god.in$ 中读入数据。
第一行两个数 $N,M$ 表示一张 $N$ 个点 $M$ 条边的图。
第二行 $N$ 个数 $a[i]$ 表示点权。
接下来 $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;
}
最后修改:2021 年 02 月 12 日 04 : 44 PM
如果觉得我的文章对你有用,请随意赞赏