Reading books /// Prim+BFS oj21633

题目大意：

输入 N,M

接下来1-N行输入读该书的用时time[i]

接下来1-M行输入a,b  表示a和b是similar的

若a读过则读b用时为 time[b]/2 ,若b读过则读a用时为 time[a]/2

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

Hint

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.

 

思路：

把每本书当做图的一个点 similar则表示两点之间存在无向路径 

Prim找出最短用时的没读过的书 sum+读该书用时 标为已读

将更新距离dis[]的部分换为BFS 搜索与该书similar的其他没读过的书 直到所有书都读过

 

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
int a[105],first[105],to[10000];
int u[10000],v[10000],vis[105];
int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m)&&(n||m))
    {
        for(int i=0;i<n;i++)
            scanf("%d",&a[i]); //读每本书的时间

        memset(first,-1,sizeof(first));
        for(int i=0;i<m;i++)
        {
            scanf("%d%d",&u[i],&v[i]);
            to[i]=first[u[i]];
            first[u[i]]=i;
        }
        for(int i=0;i<m;i++)
        {
            u[i+m]=v[i], v[i+m]=u[i];
            to[i+m]=first[v[i]];
            first[v[i]]=i+m;
        } /// 建立邻接表 正反向

        int sum=0;
        memset(vis,0,sizeof(vis));
        while(1) /// Prim部分
        {
            int mini=INF,index=0;
            for(int i=0;i<n;i++)
                if(a[i]<mini&&!vis[i])
                    mini=a[i], index=i;  /// 找到用时最短且没读过的书
            if(mini==INF) break; /// 当mini没有被交换 说明没有书没读过

            sum+=mini; vis[index]=1;

            queue <int> q; q.push(index); 
            while(!q.empty()) // BFS
            {
                int k=first[q.front()]; q.pop();
                while(k!=-1) /// 邻接表遍历
                {
                    if(!vis[v[k]])
                    { /// 将与该书similar且未没读过的书也读了 并存入队列
                        sum+=a[v[k]]/2; 
                        vis[v[k]]=1; // 标记为读过
                        q.push(v[k]);
                    }
                    k=to[k];
                }
            } /// 直到队列中这一连串的similar都被读过 则结束
        }

        printf("%d
",sum);
    }
    return 0;
}