B

B - 小Y上学记——小Y的玩偶

Time Limit: 2000/1000MS (Java/Others)    Memory Limit: 128000/64000KB (Java/Others)

Submit Status

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[3*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!=0;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=0;
    for(i=First[x];i!=0;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=1;
        for(i=1;i<=N;i++)
        {
            scanf("%d",&NUM[i]);
            Poi[i].ID=i;
            Poi[i].V=NUM[i];
            First[i]=0;
        }
        sort(Poi+1,Poi+N+1,cmp);
        for(i=1;i<=N;i++)
        {
            scanf("%d",&K);
            while(K--)
            {
                scanf("%d",&M);M+=1;
                Add_E(i,M,NUM[M]);
            }
        }
        Sum=0;
        for(i=1;i<=N;i++)
        {
            Sum+=GET_Sum(Poi[i].ID);
        }
        printf("%d
",Sum);
   }
   return 0;
}