B - 小Y上学记——小Y的玩偶
Time Limit: 2000/1000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)
Problem Description
小Y最喜欢拆拆拆了~尽管他不一定能装回去。
小Y有一个很可爱的积木玩偶，是由一块一块积木拼接而成，现在小Y想把这个积木玩偶拆拆拆。
每一块积木玩偶都有一个耐久值，想把一块积木拆出来，小Y需要付出的能量就是和它直接拼接的所有积木的耐久值之和。
小Y很懒的~他想知道把这个玩偶全部拆好，最少需要付出多少能量？
Input
多组数据，每组数据首先是一个整数n表示积木块数。(0<n<=1000)
接下来一行包含n个整数，表示每块积木的耐久值a[i](0<=a[i]<=100000)。
接下来是n行，第i行代表第i块积木的连接情况。
每一行首先是一个整数k，表示这块积木与k块积木相连，接下来是k个整数，代表与这块积木相连的积木标号(标号从0开始)
保证连接情况合法。
Output
对于每组数据，输出一个整数，表示小Y需要的最少能量。
Sample Input
4
10 20 30 40
2 1 3
2 0 2
1 1
1 0
4
100 100 100 100
1 1
3 0 2 3
2 1 3
2 1 2
7
40 10 20 10 20 80 40
4 2 3 4 5
1 4
2 0 3
5 0 2 4 5 6
4 0 1 3 6
2 0 3
2 3 4
Sample Output
40
400
160
Hint
对于第一组数据，首先拆掉第2块积木，需要20能量，然后拆掉第1块积木，需要10能量，接着拆掉第3块积木，需要10能量，最后只剩下第0块了，不需要能量了。总共需要40点能量。
对于第二组数据，无论怎么拆除，都是需要400点能量。
解法：贪心+邻接表（矩阵也可以）
每次拿走耐久度最大的点，更新图，在重复拿走，直到都成为独立的点即可。
为何要拿走耐久度最大的点，假如这个点的耐久度为K，有m条边，每一条边的所连接的点的耐久度为Ki，如果不拿走这个点的话，需要拆了可连接他的m条边的点，则是需要消耗K*m能量，如果直接把这个点拆除了，则只是需要K1+K2+...+Km能量。
因为，K*m>=K1+K2+...+Km,，细分下来，可以知道，每次拆除耐久度最大的点可以保证消耗的能量最小。再去更新连接图即可。
代码：2015.7.31
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define MAX 100010
using namespace std;
int First[MAX];
int SIGN;
struct edge{int TO,Next,Vlaue;}ID[*MAX];
struct Node{int ID,V;}Poi[MAX];
int cmp(Node a,Node b){return a.V>b.V;};
void Add_E(int x,int y,int z)
{
ID[SIGN].TO=y;
ID[SIGN].Vlaue=z;
ID[SIGN].Next=First[x];
First[x]=SIGN++;
}
void Add_E(int x,int y)
{
ID[SIGN].TO=y;
ID[SIGN].Next=First[x];
First[x]=SIGN++;
}
void Dele_x_y(int x,int y)/*删除x-y的边*/
{
int i,j;/*起始点要注意*/
for(i=j=First[x];i!=;j=i,i=ID[i].Next)
{
if(ID[i].TO==y)/*如果能够找到该边*/
{
if(i==j)First[x]=ID[i].Next;
ID[j].Next=ID[i].Next;
break;
}
}
return ;
}
int GET_Sum(int x)/*查找与X相连的顶点*/
{
int i,Sum=;
for(i=First[x];i!=;i=ID[i].Next) //查找与该点相关的点
{
Sum+=ID[i].Vlaue;
Dele_x_y(ID[i].TO,x);
}
return Sum;
} int main()
{
int N,M,K,i,j,k;
int x,y,z,Sum;
int NUM[MAX];
while(scanf("%d",&N)!=EOF)
{
SIGN=;
for(i=;i<=N;i++)
{
scanf("%d",&NUM[i]);
Poi[i].ID=i;
Poi[i].V=NUM[i];
First[i]=;
}
sort(Poi+,Poi+N+,cmp);
for(i=;i<=N;i++)
{
scanf("%d",&K);
while(K--)
{
scanf("%d",&M);M+=;
Add_E(i,M,NUM[M]);
}
}
Sum=;
for(i=;i<=N;i++)
{
Sum+=GET_Sum(Poi[i].ID);
}
printf("%d\n",Sum);
}
return ;
}