首页 > 代码库 > QS Network(最小生成树)
QS Network(最小生成树)
题意:若两个QS之间要想连网,除了它们间网线的费用外,两者都要买适配器, 求使所有的QS都能连网的最小费用。
分析:这个除了边的权值外,顶点也有权值,因此要想求最小价值,必须算边及顶点的权值和。
解决方法:用prim算法,在构造邻接矩阵时,在i到j的权值的基础上再加上i点的权值和j点的权值即可。
附上AC代码:
#include <stdio.h>#include <string.h>#include <stdlib.h>#define infinity 1000000#include<iostream>#include<algorithm>using namespace std;int N;int G[501][501];int QS[1000];int lowcost[100000],closeset[100000];int used[100000];int prim(int vcount){ int sum=0; int i,j,k; int min; for (i=0; i<vcount; i++) { lowcost[i]=G[0][i]; closeset[i]=0; used[i]=0; } used[0]=1; for (i=1; i<=vcount-1; i++) { j=0; min = infinity; for (k=1; k<vcount; k++) if ((!used[k])&&(lowcost[k]<min)) { min =lowcost[k]; j=k; } used[j]=1; sum+=min; for (k=1; k<vcount; k++) if (!used[k]&&(G[j][k]<lowcost[k])) { lowcost[k]=G[j][k]; closeset[k]=j; } } return sum;}int main(){ int t,i,j,n,sum; scanf("%d",&t); while(t--) { scanf("%d",&n); for(i=0;i<n;i++) scanf("%d",&QS[i]); for(i=0;i<n;i++) { for(j=0;j<n;j++) { scanf("%d",&G[i][j]); G[i][j]=G[i][j]+QS[i]+QS[j]; } } sum=prim(n); printf("%d\n",sum); } return 0;}
prim算法详见:http://www.cnblogs.com/PJQOOO/p/3855017.html。我是按照这个学的最小生成树。
————Anonymous.PJQ
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。