赞
踩
通过分析题目我们容易知道:
相对于一般的MST来说,这一题不同的地方在于我们需要选取某些点作为基站,而建立基站是需要花费的。而一般的MST对于一张图来说只会存在边权,对于每个点是不会存在权值的。
所以我们对这类题的处理方法是:建立虚点
那么为什么要建立虚点呢?
我们可以知道这一题的任意点都是可以建立基站的。打个比方:假如有三个城市A B C,对应的每个城市建立基站所需花费为1 1 2,A到B花费1,B到C花费2,A到C花费3。
此时如果只建立一个基站的话(假设为A),总花费最小值为:1(基站花费)+1(A到B)+2(B到C)=4
而如果建立两个基站的话(明显为A和C),此时总花费为1(A基站花费)+1(C基站花费)+1(A到B)=3
但是如果建立两个基站,A与C则无法连接,无法构成一棵树,这时就需要建立虚点来连接基站。
了解了为什么要建立虚点,我们就需要知道虚点如何建立。
我们建立虚点目的就是连接需要建立基站的点,其实简单来说虚点也是一个点,它与实点之间的权值就是每个点上建立基站所需要的花费。
抽象一点来说,这一个虚点连接了所有的实点,相当于一个超级源点,它与每一个点之间的权值就是每一个点所具有的点权,也就是所谓的建立基站的花费。
大概理解题意后我们就可以开始写代码了。
这里用到了MST的Prime算法
有不懂的小伙伴可以去看看大佬写的模板Prime算法详解
#include<cstdio> #include<iostream> #include<algorithm> #include<string.h> typedef long long ll; const int INF=0x3f3f3f3f; const int maxn=3e2+7; using namespace std; int vis[maxn];//记录点是否加入 int w[maxn][maxn];//i到j的权重 int dis[maxn];//记录其他点到i的最小距离 int Prime(int n) { memset(vis,0,sizeof(vis));//将vis数组清零意为还未加入任一点 int ans=0; vis[0]=1;//主函数中w[0][i]代表虚点到所有实点的权值,这里的vis[0]=1则是将这个超级源点加入vis,从超级源点出发 for(int i=1;i<=n;i++) { dis[i]=w[0][i];//将dis[i]更新为超级源点到所有点的权值 } for(int i=0;i<n;i++) { int k,temp=INF; for(int j=0;j<=n;j++)//在所有点未进入vis数组的点中找到权值最小的那一个 { if(!vis[j]&&dis[j]<temp) { k=j; temp=dis[j]; } } vis[k]=1;//将已找到的点加入vis数组 ans+=temp;//将找到的最小值加入答案中 for(int j=1;j<=n;j++)//将dis[]数组更新为当前找到的点到其他点的距离 { if(!vis[j]&&dis[j]>w[k][j]) { dis[j]=w[k][j]; } } } return ans; } int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&w[0][i]);//建立虚点 } for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { scanf("%d",&w[i][j]);//邻接矩阵存图 } } printf("%d",Prime(n));//直接输出答案即可 return 0; }
详解全在代码里了
本蒟蒻刚学MST,欢迎大佬们来指正我的问题
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。