最小生成树 prime算法 UVALive - 6437

时间:2022-03-25 18:10:20

题目链接:https://vjudge.net/contest/241341#problem/D

这里有多个发电站,需要求出所有点都和发电站直接或间接相连的最小代价,那么就是求出最小生成树的问题了,有点细微的不同是我们一开始要把所有的发电站看成起点(看成一个点),把其他点到发电站的最小代价求出,之后就是模板题了。

代码:

#include<iostream>
#include<cstring>
using namespace std;
const int inf=0x3f3f3f;
int map[][],vis[],ss[],dis[];
int n,m,k,t,ans;
void prime()
{
for(int i=;i<=k;i++)//多加了一层循环,遍历所有发电站
{
for(int j=;j<=n;j++)
{
dis[j]=min(dis[j],map[ss[i]][j]);
}
}
for(int i=;i<n;i++)
{
int min1=inf,u=;
for(int j=;j<=n;j++)
{
if(!vis[j]&&dis[j]<min1)
{
min1=dis[j];
u=j;
}
}
if(u==) //结束
return;
vis[u]=;
ans+=min1;
for(int j=;j<=n;j++)
{
if(!vis[j]&&dis[j]>map[u][j])
{
dis[j]=map[u][j];
}
}
}
}
int main()
{
cin>>t;
int count1=;
while(t--)
{
cin>>n>>m>>k;
memset(vis,,sizeof(vis));
int u,v,w;
memset(dis,0x3f,sizeof(dis));
memset(map,0x3f,sizeof(map));
for(int i=;i<=k;i++)
{
cin>>ss[i]; //ss数组用来保存发电站
vis[ss[i]]=; //标记为已经走过
dis[ss[i]]=; //自己到自己为0
}
for(int i=;i<=m;i++)
{
cin>>u>>v>>w;
if(map[u][v]>w)
map[u][v]=map[v][u]=w;
}
ans=;
prime();
cout<<"Case #"<<++count1<<": "<<ans<<endl;
}
return ;
}