本文主要是介绍poj 2349 Arctic Network uva 10369（prim or kruscal最小生成树），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目很麻烦，因为不熟悉最小生成树的算法调试了好久。
感觉网上的题目解释都没说得很清楚，不适合新手。自己写一个。
题意：给你点的坐标，然后两点间可以有两种方式来通信：第一种是卫星通信，第二种是无线电通信。
卫星通信：任何两个有卫星频道的点间都可以直接建立连接，与点间的距离无关；
无线电通信：两个点之间的距离不能超过D，无线电收发器的功率越大，D越大，越昂贵。
计算无线电收发器D的最小值，保证每两个点之间都有一条直接或间接的通路。
这题巧在卫星通信，也是难理解的地方。其实就相当于把一棵树去掉一条边，成为两片森林，两颗卫星就可以连接起这两片森林了。
所以，用最小生成树的算法求出最小生成树的边，有几颗卫星就可以得到几片森林，所以使用卫星而去掉的边肯定从最大的开始。
即为最小生成树的边排序后，求有m颗卫星，去掉了m-1条边后的最大边的长度。
思路明确了就看代码。
prim的算法参考了一个大神的代码，大神就是大神。
代码用了两个小技巧，一个是距离的开方在最后输出答案的时候再开，第二个是直接从小到大排序，倒回来输出（正序的第m-1个边就是逆序的第n - m个边）。
prim代码：
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;const int MaxN = 501;
const int INF = 0x3f3f3f3f;int n, m, g[MaxN][MaxN];void init()
{int point[MaxN][2];scanf("%d%d", &m, &n);for(int i = 1; i <= n; i++){scanf("%d%d", &point[i][0], &point[i][1]);}for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){if(i == j)g[i][j] = 0;elseg[i][j] = INF;}}for(int i = 1; i <= n; i++){for(int j = i + 1; j <= n; j++){g[i][j] = g[j][i] = (point[i][0]-point[j][0])*(point[i][0]-point[j][0]) + (point[i][1]-point[j][1])*(point[i][1]-point[j][1]);//printf("-------%d-------\n", g[i][j]);}}
}void prim()
{bool vis[MaxN];int dis[MaxN];int lowcost[MaxN];for(int j = 1; j <= n; j++){//dis[j] = INF;vis[j] = false;lowcost[j] = 0;dis[j] = g[1][j];//debug}dis[1] = 0;vis[1] = true;int count = 0;for(int i = 1; i < n; i++){int mark = -1, mindis = INF;for(int j = 1; j <= n; j++){if(!vis[j] && dis[j] < mindis){mindis = dis[j];mark = j;}}vis[mark] = true;lowcost[count++] = mindis;for(int j = 1; j <=n; j++){if(!vis[j] && dis[j] > g[mark][j]){dis[j] = g[mark][j];}}}sort(lowcost, lowcost + n);//for(int i = 1; i <= n; i++)printf("%.2f\n", sqrt((double)lowcost[n - m]));
}int main()
{//freopen("in.txt", "r", stdin);int ncases;scanf("%d", &ncases);while(ncases--){init();prim();}return 0;
}
脑袋糊糊的荡了个代码改了一个kruscal，开始的时候RE了，是因为边的数组开的不够大。
这种写法还真是又长又臭。效率远远低于第一种。
代码：
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;const int MaxN = 501;int fa[MaxN];
int l;//边个数
int m;
int n;//点个数struct point
{int x,y;
} p[MaxN];struct edge
{int u,v;double w;bool operator<(const edge &b)const{return w < b.w;}
} e[250010];void init()
{for(int i = 0 ; i < n ; i++){fa[i] = i;}
}int find(int x)
{if(x != fa[x])fa[x] = find(fa[x]);return fa[x];
}void unin(int x,int y)
{int a = find(x);int b = find(y);if(a != b)fa[b] = a;
}void kruscal()
{int key = 0;sort(e, e + l);init();for(int i = 0 ; i < l ; i++){int t1 = find(e[i].u);int t2 = find(e[i].v);if(t1 != t2){key++;unin(e[i].u,e[i].v);if(key == n - m){printf("%.2f\n",sqrt((double)e[i].w));}}}
}int main()
{//freopen("in.txt", "r", stdin);int ncases;scanf("%d", &ncases);while(ncases--){scanf("%d%d", &m, &n);for(int i = 0 ; i < n ; i++){scanf("%d%d", &p[i].x, &p[i].y);}l = 0;for(int i = 0 ; i < n ; i++){for(int j = 0 ; j < n ; j++){if(i!=j){e[l].v = i;e[l].u = j;e[l++].w = (p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y - p[j].y)*(p[i].y - p[j].y);}}}kruscal();}return 0;
}
一放假就就空虚，什么都不想做。
脖子上的东西又想太多。
这篇关于poj 2349 Arctic Network uva 10369（prim or kruscal最小生成树）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
