题意：给你一个n^2的邻接矩阵，表示u到v的距离，问你要让所以农场通网需要多长网线。
题解：用prim算法，从一个结点开始构造生成树，每次选当前子图和图外结点权值最小的边，把图外结点加入子图中。
prim比kruskal更适合稠密图，未优化的prim时间复杂的为O(u^2),kruskal时间复杂的为O(eloge)
1 #include <cstdio> 2 #include <cstring> 3 using namespace std; 4 const int inf = 0x3f3f3f3f; 5 int cost[110][110], lowc[110], vis[110]; 6 int n; 7 ?8 int prim() 9 {10 ????memset(vis,0,sizeof(vis));11 ????int minc,res=0,p;12 ????vis[0]=1;13 ????for(int i=0;i<n;i++)14 ????????lowc[i]=cost[0][i];15 ????for(int i=1;i<n;i++)16 ????{17 ????????minc=inf;18 ????????p=-1;19 ????????for(int j=0;j<n;j++)20 ????????{21 ????????????if(vis[j]==0&&lowc[j]<minc)22 ????????????{23 ????????????????minc=lowc[j];24 ????????????????p=j;25 ????????????}26 ????????}27 ????????if(minc==inf)28 ????????????return -1;29 ????????res+=minc;30 ????????vis[p]=1;31 ????????for(int j=0;j<n;j++)32 ????????????if(vis[j]==0&&lowc[j]>cost[p][j])33 ????????????????lowc[j]=cost[p][j];34 ????}35 ????return res;36 }37 38 int main()39 {40 ????while(~scanf("%d", &n) && n)41 ????{42 ????????for(int i = 0; i < n; i++)43 ????????????for(int j = 0; j < n; j++)44 ????????????????scanf("%d", &cost[i][j]);45 ????????printf("%d\n", prim());46 ????}47 }POJ 1258 Agri-Net
原文地址：http://www.cnblogs.com/kearon/p/7669129.html