題目大意

????給定N個點的坐標，這N個點之間需要進行通訊。通訊方式可以采用衛(wèi)星通信或無線通信，若兩點之間采用為衛(wèi)星通信，則兩點之間的距離無限制，若采用無線通訊，則兩點之間的距離不能大于某個值D。?
????現(xiàn)有s臺衛(wèi)星通信設(shè)備可以分配給這N個點，其余的點之間必須使用無線通信。要讓這N個點中所有的點都能相互通信，則合理分配s臺衛(wèi)星通信設(shè)備，可以使得采用無線通信的那些點之間的距離D達到一個最小值，求該最小值。

題目分析

????讓所有的點之間均能通信，為一個生成樹結(jié)構(gòu)。題目就是求出這N個點的最小生成樹。然后將最小生成樹分成S個割集，割集之間采用衛(wèi)星通信，割集之內(nèi)采用無線通信，求出割集之內(nèi)點之間的最大值即可。?
????可以證明，割集之內(nèi)的點距離的最大值的最小值為最小生成樹的N-1條邊從大到小排列后第S個邊長。采用kruskal算法解決。

實現(xiàn)(c++)

#include<stdio.h> #include<queue> #include<vector> #include<cmath> using namespace std; #define MAX_NODE 505 //點的數(shù)據(jù)結(jié)構(gòu) struct Point{int x;int y; }; vector<Point> gPoints;//邊的數(shù)據(jù)結(jié)構(gòu) struct Edge{int from;int to;double dist;Edge(int f, int t, double d) :from(f), to(t), dist(d){}; }; vector<Edge> gEdges;//計算兩點之間的距離 double Dist(const Point& p1, const Point& p2){return sqrt(1.0*(p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y)); }//用并查集來判斷加入一條邊是否會構(gòu)成環(huán) int gRoot[MAX_NODE]; int GetRoot(int c){if (gRoot[c] != c){gRoot[c] = GetRoot(gRoot[c]);}return gRoot[c]; } bool SameRoot(int c1, int c2){int p1 = GetRoot(c1);int p2 = GetRoot(c2);return p1 == p2; }void Union(int c1, int c2){int p1 = GetRoot(c1);int p2 = GetRoot(c2);gRoot[p1] = p2; } //用于對邊進行排序 bool Compare(const Edge& e1, const Edge& e2){return e1.dist < e2.dist; }double Kruskal(int s, int n){double result;for (int i = 0; i < n; i++){gRoot[i] = i;}sort(gEdges.begin(), gEdges.end(), Compare); //無向圖的邊只存儲了 從序號較小的節(jié)點指向序號較大的節(jié)點int count = 0;for (int i = 0; i < gEdges.size(); i++){Edge& e = gEdges[i];if (SameRoot(e.from, e.to))continue;count++;if (count == n - s){ //從最小生成樹中的n-1條邊，去掉最大的s-1條邊（因為有s個衛(wèi)星站，相當于s個點，則s-1條邊）//，剩下的n-1-s條邊中，最大的邊長即為所求result = e.dist;return result;}Union(e.to, e.from);//gRoot[gRoot[e.to]] = gRoot[e.from]; //注意合并的時候，將 to 的根更新為 from的根。因為所有的邊只存儲了從小序號指向大序號}return 0; }int main(){int cas, s, p;Point point;scanf("%d", &cas);while (cas--){scanf("%d %d", &s, &p);gEdges.clear();gPoints.clear();for (int i = 0; i < p; i++){scanf("%d %d", &point.x, &point.y);for (int j = 0; j < i; j++){double dist = Dist(point, gPoints[j]);gEdges.push_back(Edge(j, i, dist));}gPoints.push_back(point);}double result = Kruskal(s, p);printf("%.2lf\n", result);}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/gtarcoder/p/4867404.html

總結(jié)

以上是生活随笔為你收集整理的poj_2349 Kruskal 最小生成树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。