NOIP-普里姆算法

题目描述：

        FarmerJohn被选为他们镇的镇长!他其中一个竞选承诺就是在镇上建立起互联网，并连接到所有的农场。当然，他需要你的帮助。约翰已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。为了用最小的消费，他想铺设最短的光纤去连接所有的农场。你将得到一份各农场之间连接费用的列表，你必须找出能连接所有农场并所用光纤最短的方案。每两个农场间的距离不会超过100,000。

输入格式：

第一行一个整数n(3<=n<=100)个农场的个数。

以下n行，描述一个n*n的矩阵,表示每个农场之间的距离。

理论上，他们是n行，每行由n个用空格分隔的数组成，实际上，他们限制在80个字符，因此，某些行会紧接着另一些行。当然，对角线是0(没有环)。

输出格式

输出一行一个整数，表示连接到每个农场的光纤的最小长度总和。

输入输出样例：

agrinet.in

4

0 4 9 21

4 0 8 17

9 8 0 16

21 17 16 0

agrinet.out

28

---

解题报告：

        该算法题属于最小生成树类型的题目，最小生成树又叫MST(Minimum Cost SpanningTree)，由两种常用算法解决，普里姆算法和克鲁斯卡尔算法。其中Prim算法基于“选点”，Kruskal算法基于“选边”；因此Kruskal算法会用到并查集，因为涉及到合并操作。

        此次使用基于邻接矩阵实现的Prim算法,因为注意到 n<=100。

        代码中已经给出注释，如果对算法不了解，可以构造一颗符合条件的图，或者使用样例模拟一遍基本就清楚了。

---

# include

using namespace std;

const int INF = 0x3f3f3f3f;

const int MAXN = 5000;

int cost[MAXN][MAXN];//邻接矩阵,如果时有向图那么要用INF表示不邻接

int vis[MAXN];

int lowc[MAXN];

int prim(int cost[][MAXN],int n){

     //初始化

     int minc,res = 0,p;

     memset(vis,0, sizeof(vis));

     vis[0] =1; //从0节点开始访问

    

     //从0到其他节点的权值保存到lowc数组里

     for(int i = 1; i < n; i++)

         lowc[i]= cost[0][i];

     //循环n-1次得到最小生成树

     for(int k = 1; k < n; k++){

         minc = INF;

         p = -1;

         //j代表结点, 找lowc[]数组中最小的,就是从点集出发最小的边

         for(int j = 0; j < n; j++){

              if(vis[j]== 0 && lowc[j] < minc){

                   minc= lowc[j];  p = j;

              }

         }

         if(INF == minc) return -1;//表示此图不通

         res += minc;

         vis[p] = 1;//标记该点加进来

         //更新由该点出发是否造成lowc数组减小

         for(int j = 0; j < n; j++){

              if(vis[j] == 0 && cost[p][j] < lowc[j])

                   lowc[j]= cost[p][j];

         }

     }

     return res;

}

int main(){

     int n;

     cin >> n;

     for(int i =0;i

         for(int j =0;j

              cin >> cost[i][j];

         }

     }

     cout << prim(cost,n);

     return 0;

}

---