Agri-Net POJ - 1258 最小生成树值Prim算法

  1 #include <cstdio>
  2 #include <fstream>
  3 #include <algorithm>
  4 #include <cmath>
  5 #include <deque>
  6 #include <vector>
  7 #include <queue>
  8 #include <string>
  9 #include <cstring>
 10 #include <map>
 11 #include <stack>
 12 #include <set>
 13 #include <sstream>
 14 #include <iostream>
 15 #define mod 998244353
 16 #define eps 1e-6
 17 #define ll long long
 18 #define INF 0x3f3f3f3f
 19 using namespace std;
 20 
 21 //存放地图
 22 int ma[100][100];
 23 //lowcost存放到起点的距离
 24 //mst表示i指向的点，
 25 int lowcost[100],mst[100];
 26 //n表示点数
 27 int n;
 28 //初始化地图
 29 void init()
 30 {
 31     for(int i=0;i<=n;i++)
 32     {
 33         for(int j=0;j<=n;j++)
 34         {
 35             //本地到本地的权值为0，到其他点的权值为无穷
 36             if(i==j)
 37             {
 38                 ma[i][j]=0;
 39             }
 40             else
 41             {
 42                 ma[i][j]=INF;
 43             }
 44         }
 45     }
 46 }
 47 //u表示起点
 48 int prim(int u)
 49 {
 50     //ans表示树上所有边的权值和
 51     int ans=0;
 52     //初始化lowcost,mst
 53     for(int i=1;i<=n;i++)
 54     {
 55         //将所有指向起点的边录入lowcost中
 56         lowcost[i] = ma[u][i];
 57         //所有的点都指向起点
 58         mst[i]=u;
 59     }
 60     //起点已在树上，所以为-1
 61     mst[u] = -1;
 62     //遍历其他n-1个点
 63     for(int i=1;i<n;i++)
 64     {
 65         //当前最小权值为INF
 66         int mi=INF;
 67         //当前最小值指向的点是-1
 68         int v=-1;
 69         //遍历所有的点
 70         for(int j=1;j<=n;j++)
 71         {
 72             //如果该点不在树上，且该点到起点的距离小于当前最小权值
 73             if(mst[j]!=-1&&lowcost[j]<mi)
 74             {
 75                 //记录这个较小的点和权值
 76                 v=j;
 77                 mi=lowcost[j];
 78             }
 79         }
 80         //v！=-1表示在所有与树连接的最小权值
 81         if(v!=-1)
 82         {
 83             //将这个点标记
 84             mst[v]=-1;
 85             //累计这个边的权值
 86             ans+=lowcost[v];
 87             //遍所有的点
 88             for(int j=1;j<=n;j++)
 89             {
 90                 //如果j不在树上且j到树上的距离比j到v的距离大
 91                 //更新这个数据，并将mst[j]指向v
 92                 if(mst[j]!=-1&&lowcost[j]>ma[v][j])
 93                 {
 94                     lowcost[j]=ma[v][j];
 95                     mst[j]=v;
 96                 }
 97             }
 98         }
 99     }
100     //返回树上所有边的权值和
101     return ans;
102 }
103 int main()
104 {
105     while(scanf("%d",&n)!=EOF)
106     {
107         init();
108         for(int i=1;i<=n;i++)
109         {
110             for(int j=1;j<=n;j++)
111             {
112                 scanf("%d",&ma[i][j]);
113             }
114         }
115         printf("%d\n",prim(1));
116     }
117 }