本文共 1737 字，大约阅读时间需要 5 分钟。
题目链接：
题目大意：
给定平面上N个城市的位置，计算连接这N个城市所需线路长度总和的最小值。
思路：
模板题
最小生成树，Prim求解。注意两个城市之间都有一条边相连。还有每两组输出之间空一行。
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 using namespace std;11 typedef long long ll;12 const int maxn = 2e2 + 10;13 const int INF = 1 << 30;14 int dir[4][2] = { 1,0,0,1,-1,0,0,-1};15 int T, n, m;16 double Map[maxn][maxn];//存图17 double lowcost[maxn];18 int mst[maxn];19 void prim(int u)//最小生成树起点20 {21 double sum_mst = 0;//最小生成树权值22 for(int i = 1; i <= n; i++)//初始化两个数组23 {24 lowcost[i] = Map[u][i];25 mst[i] = u;26 }27 mst[u] = -1;//设置成-1表示已经加入mst28 for(int i = 1; i <= n; i++)29 {30 double minn = 1.0 * INF;31 int v = -1;32 //在lowcost数组中寻找未加入mst的最小值33 for(int j = 1; j <= n; j++)34 {35 if(mst[j] != -1 && lowcost[j] < minn)36 {37 v = j;38 minn = lowcost[j];39 }40 }41 if(v != -1)//v=-1表示未找到最小的边,42 { //v表示当前距离mst最短的点43 //printf("%d %d %d\n", mst[v], v, lowcost[v]);//输出路径44 mst[v] = -1;45 sum_mst += lowcost[v];46 for(int j = 1; j <= n; j++)//更新最短边47 {48 if(mst[j] != -1 && lowcost[j] > Map[v][j])49 {50 lowcost[j] = Map[v][j];51 mst[j] = v;52 }53 }54 }55 }56 //printf("weight of mst is %d\n", sum_mst);57 printf("The minimal distance is: %.2f\n", sum_mst);58 }59 double x[105], y[105];60 int cases;61 int main()62 {63 while(cin >> n && n)64 {65 if(cases)cout< > x[i] >> y[i];67 for(int i = 1; i <= n; i++)68 {69 for(int j = 1; j <= n; j++)70 {71 Map[i][j] = sqrt((x[j] - x[i]) * (x[j] - x[i]) + (y[j] - y[i]) * (y[j] - y[i]));72 }73 }74 printf("Case #%d:\n", ++cases);75 prim(1);76 }77 return 0;78 }
转载于:https://www.cnblogs.com/fzl194/p/8724459.html