首页 > 其他 > 详细

GDCPC 2008:B Reading books

时间:2014-05-30 10:03:34      阅读:358      评论:0      收藏:0      [点我收藏+]

Problem B

Reading books

(Input File: book.in / Standard Output)

 

In the summer vacation, LRJ wants to improve himself in computer science. So he finds out N books of computer science in the school library. The books are numbered from 0 to N-1.

To finish reading the i-th book, it takes LRJ time[i] minutes. But some books are similar in the content. If the i-th book and the j-th book are similar, then if LRJ has finished reading the i-th book, it will take him only  minutes to finish reading the j-th book. Of course if LRJ has finished reading the j-th book, it will take him only  minutes to finish reading the i-th book. Now you are asked to tell LRJ the minimal total time to finish reading all the N books.

 

Input:

The first line contains two integers N (0<=N<=100) and M (0<=M<=N*(N-1)/2). N is the total number of books. M is the number of pairs which are similar.

Then the following N lines describe time[0], time[1], … , time[N-1] (1<=time[i]<=105).

Next comes M lines, each contains two integer (i, j), indicating that the i-th book and the j-th book are similar.

Input is ended by N=0 and M=0.

 

Output:

For each test case, just output the minimal total time on a single line.

 

Sample input:

2 1

6

10

0 1

3 2

1

2

3

0 1

1 2

3 1

2

4

6

0 1

0 0

 

Sample output:

11

3

10

 

Hints:

For the first test case, if LRJ read the books in the order (0, 1), then the total time = 6+10/2=11; If in the order (1, 0), then the total time =10+ 6/2=13.

 

用矩阵将全部相似的书都标记起来,然后通过dfs去算和就可以

 

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

int map[105][105],val[105],n,m,sum,minn;
int vis[105],ans;

void dfs(int x)
{
    vis[x] = 1;
    sum+=val[x]/2;
    if(minn == -1 || val[x]<minn)
        minn = val[x];
    for(int i = 0; i<n; i++)
    {
        if(!vis[i] && map[x][i])
            dfs(i);
    }
}

int main()
{
    int i,x,y;
    while(~scanf("%d%d",&n,&m),n+m)
    {
        memset(map,0,sizeof(map));
        memset(vis,0,sizeof(vis));
        ans = 0;
        for(i = 0; i<n; i++)
            scanf("%d",&val[i]);
        for(i = 0; i<m; i++)
        {
            scanf("%d%d",&x,&y);
            map[x][y] = map[y][x] = 1;
        }
        for(i = 0; i<n; i++)
        {
            minn = -1;
            if(vis[i])
                continue;
            sum = 0;
            dfs(i);
            ans = ans+sum-minn/2+minn;
        }
        printf("%d\n",ans);
    }

    return 0;
}


 

GDCPC 2008:B Reading books,布布扣,bubuko.com

GDCPC 2008:B Reading books

原文:http://www.cnblogs.com/blfshiye/p/3756353.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!