首页 > 代码库 > Codeforces Round #250 (Div. 2) C. The Child and Toy 详解

Codeforces Round #250 (Div. 2) C. The Child and Toy 详解

2024-07-23 21:38:26   226人阅读

output
standard output

On Children‘s Day, the child got a toy from Delayyy as a present. However, the child is so naughty that he can‘t wait to destroy the toy.

The toy consists of n parts and m ropes. Each rope links two parts, but every pair of parts is linked by at most one rope. To split the toy, the child must remove all its parts. The child can remove a single part at a time, and each remove consume an energy. Let‘s define an energy value of part i as vi. The child spendvf1?+?vf2?+?...?+?vfk energy for removing part i where f1,?f2,?...,?fk are the parts that are directly connected to the i-th and haven‘t been removed.

Help the child to find out, what is the minimum total energy he should spend to remove alln parts.

Input

The first line contains two integers n andm (1?≤?n?≤?1000;0?≤?m?≤?2000). The second line contains n integers: v1,?v2,?...,?vn (0?≤?vi?≤?105). Then followedm lines, each line contains two integers xi andyi, representing a rope from partxi to partyi (1?≤?xi,?yi?≤?n; xi?≠?yi).

Consider all the parts are numbered from 1 to n.

Output

Output the minimum total energy the child should spend to remove all n parts of the toy.

Sample test(s)
Input
4 310 20 30 401 41 22 3
Output
40
Input
4 4100 100 100 1001 22 32 43 4
Output
400
Input
7 1040 10 20 10 20 80 401 54 74 55 25 76 41 61 34 31 4
Output
160
Note

One of the optimal sequence of actions in the first sample is:

  • First, remove part 3, cost of the action is 20.
  • Then, remove part 2, cost of the action is 10.
  • Next, remove part 4, cost of the action is 10.
  • At last, remove part 1, cost of the action is 0.

So the total energy the child paid is 20?+?10?+?10?+?0?=?40, which is the minimum.

In the second sample, the child will spend 400 no matter in what order he will remove the parts.


做了这道题，感觉很有必要写一篇题解，算是开拓思路。

题目大意就是给你一张联通图，每个点有一个权值。问你最后要把所有点都分开，剪断一条路的代价是 取这条路两端的任意一点， 找到与所有与它相连的点，并把它们的权值加起来。问最小代价。

声明：选取两端的其中一个作为“目标点”，找与“目标点”相连的点的权值之和。

看起来描述很复杂，感觉也无从下手，可以考虑一些简单的情况，复杂的图都是由简单的基本单元构成。

首先考虑k个点构成环，那么代价就很明显的剪断k-1条路，且每次剪断的最小代价就两个权值的较小值。

如果是一个点连多个点的情况，且1号节点的权值大于其余点的权值 ，比如：

这一张图，若选取2为目标点，那么sum就要加上与2相连的1的权值，3和4也是类似，都是加上1的权值。

那么考虑选取1为目标点，sum就加上2,3,4的权值，结果会更小。所以，若1号的权值比其余点大，那么取其他点的权值之和。


假设1号节点的权值比其余各点的权值都小，上图的v[1] = 1，那么最优结果是分别取其余点为目标点，每次sum加上v[1]。


假设其余节点的权值有的比1号大有的比一号小，最优的情况是把比1号权值大的分别当做目标点减去，sum加的就是v[1]*比v[1]大的个数。

剩下的就是和情况1相同了。


综合上述三种情况，可以发现最优值就是一张图里所有的边链接的两端较小的权值之和。


#include <stdio.h>
#include <string.h>
#include <math.h>
#include <iostream>
#include <queue>
#include <algorithm>
#define mem(f) memset(f,0,sizeof(f))
#define M 100005
#define mod 1000000007
#define lson o<<1, l, m
#define rson o<<1|1, m+1, r
using namespace std;
typedef __int64 LL;
const int MAX = 0x3f3f3f3f;
const int maxn = 2111111;

int n, m, a, b, v[1111], d[1111];

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)  cin >> v[i];
    int ans = 0;
    for(int i = 0; i < m; i++) {
        cin >> a >> b;
        ans += min(v[a], v[b]);
    }

    cout << ans << endl;
    return 0;
}




Codeforces Round #250 (Div. 2) C. The Child and Toy 详解


联系
我们