首页 > 代码库 > QS Network(最小生成树)

QS Network(最小生成树)

2024-07-13 02:10:33   220人阅读

题意：若两个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


联系
我们