题意：
有n个农场，已知这n个农场都互相相通，有一定的距离，现在每个农场需要装光纤，问怎么安装光纤能将所有农场都连通起来，并且要使光纤距离最小，输出安装光纤的总距离。
思路：
又是一个最小生成树，因为给出了一个二维矩阵代表他们的距离，直接算prim就行了。
代码：
#include <iostream>using namespace std;#define maxn 105#define inf 0x3f3f3f3fint map[maxn][maxn],n;void Prim(){ ???int i,j,d[maxn],vis[maxn],mi,v; ???for(i=1;i<=n;i++) ???{ ???????d[i]=map[1][i]; ???????vis[i]=0; ???} ???for(i=1;i<=n;i++) ???{ ???????mi=inf; ???????for(j=1;j<=n;j++) ???????????if(!vis[j] && d[j]<mi) ???????????{ ???????????????mi=d[j]; ???????????????v=j; ???????????} ???????vis[v]=1; ???????for(j=1;j<=n;j++) ???????????if(!vis[j] && d[j]>map[v][j]) ???????????????d[j]=map[v][j]; ???} ???for(d[0]=0,i=1;i<=n;i++) d[0]+=d[i]; ???cout<<d[0]<<endl;}int main(){ ???int i,j; ???while(cin>>n) ???{ ???????for(i=1;i<=n;i++) ???????????for(j=1;j<=n;j++) ???????????????cin>>map[i][j]; ???????Prim(); ???} ???return 0;}POJ1258 Agri-Net【最小生成树】
原文地址：http://www.cnblogs.com/darklights/p/7647610.html