http://www.dotcpp.com/oj/problem1705.html
题目描述
最小生成树问题是实际生产生活中十分重要的一类问题。假设需要在n个城市之间建立通信联络网，则连通n个城市只需要n-1条线路。这时，自然需要考虑这样一个问题，即如何在最节省经费的前提下建立这个通信网。
可以用连通网来表示n个城市以及n个城市之间可能设置的通信线路，其中网的顶点表示城市，边表示两个城市之间的线路，赋于边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。现在，需要选择一棵生成树，使总的耗费最小。这个问题就是构造连通网的最小代价生成树，简称最小生成树。一棵生成树的代价就是树上各边的代价之和。
而在常用的最小生成树构造算法中，普里姆（Prim）算法是一种非常常用的算法。以下是其算法的大致结构：
在本题中，读入一个无向图的邻接矩阵（即数组表示），建立无向图并按照以上描述中的算法建立最小生成树，并输出最小生成树的代价。
输入
输入的第一行包含一个正整数n，表示图中共有n个顶点。其中n不超过50。
以后的n行中每行有n个用空格隔开的整数，对于第i行的第j个整数，如果不为0，则表示第i个顶点和第j个顶点有直接连接且代价为相应的值，0表示没有直接连接。当i和j相等的时候，保证对应的整数为0。
输入保证邻接矩阵为对称矩阵，即输入的图一定是无向图，且保证图中只有一个连通分量。
输出
只有一个整数，即最小生成树的总代价。请注意行尾输出换行。
样例输入
4 0 2 4 0 2 0 3 5 4 3 0 1 0 5 1 0样例输出
6提示
在本题中，需要掌握图的深度优先遍历的方法，并需要掌握无向图的连通性问题的本质。通过求出无向图的连通分量和对应的生成树，应该能够对图的连通性建立更加直观和清晰的概念。
Prim算法
#include<stdio.h> #define N 120 int e[N][N],dis[N],book[N]; int main() { int i,j,k,m,n,min,count=0,sum=0,inf=99999999; scanf("%d",&n); for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(i==j) e[i][j]=0; else e[i][j]=inf; for(i=1;i<=n;i++) for(j=1;j<=n;j++) { scanf("%d",&e[i][j]); //e[j][i]=e[i][j]; if(i!=j&&e[i][j]==0) e[i][j]=e[j][i]=inf; } for(i=1;i<=n;i++) dis[i]=e[1][i]; book[1]=1; count++; while(count<n) { min=inf; for(i=1;i<=n;i++) { if(book[i]==0&&dis[i]<min) { min=dis[i]; j=i; } } book[j]=1; count++; sum=sum+dis[j]; for(k=1;k<=n;k++) { if(book[k]==0&&dis[k]>e[j][k]) dis[k]=e[j][k]; } } printf("%d\n",sum); return 0; }
