首页 > 代码库 > POJ - 2485 Highways

POJ - 2485 Highways

2024-07-15 01:29:30   228人阅读

题目来源：http://poj.org/problem?id=2485

      用贪心策略构成最小生成树，有常用的两种算法Prim算法和Kruskal算法。本题我采用的是Prim算法。

设带权图为V，首先随便选一点作为构成一个真子集S，然后在采取贪心策略，选取V-S中的某一点到S中

一点的最小距离并将该点添加进去，直到S=V。

 1 #include<stdio.h> 2 const int maxn=500+5; 3 int c[maxn][maxn],lowcost[maxn]; 4 bool s[maxn]; 5 int prime(int n) 6 { 7     s[1]=true; 8     for(int i=2;i<=n;i++){ 9         lowcost[i]=c[1][i];10         s[i]=false;11     }12     int j=1,maxlength=-1;13     for(int i=1;i<n;i++){14         int mincost=65537;15         for(int k=2;k<=n;k++)16             if(mincost>lowcost[k] && !s[k]){17                 mincost=lowcost[k];18                 j=k;19             }20         s[j]=true;21         if(maxlength<mincost)22             maxlength=mincost;23         for(int k=2;k<=n;k++)24             if(c[j][k]<lowcost[k] && !s[k])25                 lowcost[k]=c[j][k];26 27     }28     return maxlength;29 }30 int main()31 {32     int t;33     scanf("%d",&t);34     while(t--){35         int n;36         scanf("%d",&n);37         for(int i=1;i<=n;i++)38             for(int j=1;j<=n;j++)39             scanf("%d",&c[i][j]);40         int ans=prime(n);41         printf("%d\n",ans);42     }43     return 0;44 }

 


联系
我们