题目大意：
输入 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[],first[],to[];
int u[],v[],vis[];
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m)&&(n||m))
{
for(int i=;i<n;i++)
scanf("%d",&a[i]); //读每本书的时间 memset(first,-,sizeof(first));
for(int i=;i<m;i++)
{
scanf("%d%d",&u[i],&v[i]);
to[i]=first[u[i]];
first[u[i]]=i;
}
for(int i=;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=;
memset(vis,,sizeof(vis));
while() /// Prim部分
{
int mini=INF,index=;
for(int i=;i<n;i++)
if(a[i]<mini&&!vis[i])
mini=a[i], index=i; /// 找到用时最短且没读过的书
if(mini==INF) break; /// 当mini没有被交换 说明没有书没读过 sum+=mini; vis[index]=; queue <int> q; q.push(index);
while(!q.empty()) // BFS
{
int k=first[q.front()]; q.pop();
while(k!=-) /// 邻接表遍历
{
if(!vis[v[k]])
{ /// 将与该书similar且未没读过的书也读了 并存入队列
sum+=a[v[k]]/;
vis[v[k]]=; // 标记为读过
q.push(v[k]);
}
k=to[k];
}
} /// 直到队列中这一连串的similar都被读过 则结束
} printf("%d\n",sum);
}
return ;
}