题目详情
n个节点，m条边的无向图，每个节点一个权值w。定义拆除一个节点的代价为与其相邻的节点的权值之和。拆除一个节点后删除所有与该节点相连的边。求拆除所有节点需要花费的最少代价。输入描述：输入包含多组测试数据，每组测试数据第一行先输入n，m（1 ≤ n ≤ 10000; 0 ≤ m ≤ 20000），第二行输入n个整数wi（0 ≤ wi ≤ 105）,接下来的m行，每行两个整数u，v代表节点u与v相连(1 ≤ ui, vi ≤ n; ui ≠ vi).输出描述：对于每组测试数据，输出拆除所有节点需要花费的最少代价。
答题说明
样例输入：
4 3
10 20 30 40
1 4
1 2
2 3
样例输出：
40
Note：
其中一种拆除策略是：
先拆除节点3，代价为20
再拆除节点2，代价为10
再拆除节点4，代价为10
最后拆除节点1，代价为0
所以总的代价=20+10+10+0=40
解析:我以为这道题要用贪心算法:每次都删掉最小权值的点.所以我就写了这么多.答案是错误.
而实际上,没必要,每条边都要删掉的!只要把边的一端删掉就可以删掉此边了.
所以,把所有的边的权值加起来就行了.
因为所有点到最后都需要拆，则拆点的过程会涉及每一条边。因此我们对每一条边，取该边的两个顶点中权值较小的作为拆除该边的代价，最终统计拆除所有边所需要的最小代价和，即为所求解。
经验一:不要高估二星题.想的复杂了,必然不对.
经验二:换个角度看问题,别有洞天.
经验三:对过程寻求另一种描述.当我们把注意力放在点上的时候,谁能想到突破口在边上.
#include<stdio.h>
#include<string.h>
int a[10000];
int c[10000];
char b[10000][10000];
void main(){
int n, m;
int i,j, x,y;
int min;
int ans = 0;
int size;
//freopen("in.txt", "r", stdin);
memset(b, 0, sizeof(b));
memset(c, 0, sizeof(c));
scanf("%d%d", &n, &m);
size = n;
for (i = 0; i < n; i++)
scanf("%d", &a[i]);
for (i = 0; i < m; i++)
{
scanf("%d%d", &x, &y);
x--; y--;
b[x][y]=b[y][x] = 1;
c[x] += a[y];
c[y] += a[x];
}
min = 0;
for (i = 1; i < n;i++)
if (c[i] <= c[min]&&a[i]>a[min])min = i;
again:ans += c[min];
j = min;
c[j] = -1;
for (i = 0; c[i] < 0; i++);
min = i;
for (; i < n; i++)
{
if (b[j][i] == 1&&c[i]>=0)c[i] -= a[j];
if (c[i] <= c[min]&&c[i]>=0&&a[i]>a[min])min = i;
}
size--;
if(size>0)goto again;
printf("%d", ans);
}