codeforces437C

题意：给一个n个点，m条边的图，每个点有一个权值w，每删去一个点所消耗的能量为与该点相邻的点的权值之和。问消耗的最小能量是多少？

Examples

Input

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

Output

40

解析：很基础的一道图论题目，然而我并没有AC出来（QAQ）我的思路是这样的：我们首先将点的权值按贪心思想从大到小排序。这样在删除时大权值的点直接***掉了，不会被加进ans中。之后就是vector构图，用bfs进行图的遍历得到结果。不过提交上去代码是错的。。。

附上错误代码一份：

#include<iostream>
#include<algorithm>
#include<stdlib.h>
#include<stdio.h>
#include<string>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;
typedef long long ll;
const int maxn = 10000;
vector<int>vec[maxn];
struct Node {
	int w;//权值
	int num;//下标
}a[maxn];
int n, m;
bool vis[maxn];
int x, y;
int val[maxn];
bool cmp(Node p, Node q)
{
	return p.w>q.w;
}
int bfs(int u, int cnt)
{
	ll ans = 0;
	queue<int>Q;//Q里面放点的下标
	Q.push(u);
	vis[u] = 1;

	while (!Q.empty())
	{
		int v = Q.front();
		vis[v] = 1;//将待删除的点做上标记
		Q.pop();
		for (int i = 0; i<vec[v].size(); i++) {
			int t = vec[v][i];//相邻点的下标
			if (!vis[t]) {
				ans += val[t];
				cnt++;		//将次大权值的点放进队列
				Q.push(a[cnt].num);
			}
		}
	}
	return ans;
}
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &val[i]);
		a[i].w = val[i];//输入点的权值
		a[i].num = i;//输入点的下标
	}
	for (int i = 1; i <= m; i++) {
		scanf("%d%d", &x, &y);
		vec[x].push_back(y);//将下标放进vector里
		vec[y].push_back(x);
	}
	sort(a + 1, a + 1 + n, cmp);//对权值进行排序
	memset(vis, 0, sizeof(vis));
	int u = a[1].num;
	int ans = bfs(u, 1);
	printf("%d\n", ans);
	return 0;
}

最后被逼的没办法了，只好看大佬的代码，然后惊奇的发现这居然是一道数学思维题！！！跪了！

AC代码如下：

#include<iostream>
#include<algorithm>
#include<stdlib.h>
#include<stdio.h>
#include<string>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;
typedef long long ll;
const int maxn = 10000;
int a[maxn];
int n,m;
int x, y;
int main()
{
	ios::sync_with_stdio(false);
	cin >> n>>m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	int ans = 0;
	for (int i = 1; i <= m; i++) {
		cin >> x >> y;
		ans += min(a[x], a[y]);
	}
	cout<<ans<<endl;
	return 0;
}