題目大意

　　國防部計劃用無線網絡連接若干個邊防哨所。2 種不同的通訊技術用來搭建無線網絡；每個邊防哨所都要配備無線電收發器；有一些哨所還可以增配衛星電話。任意兩個配備了一條衛星電話線路的哨所（兩邊都?有衛星電話）均可以通話，無論他們相距多遠。而只通過無線電收發器通話的哨所之間的距離不能超過 D，這是受收發器的功率限制。收發器的功率越高，通話距離 D 會更遠，但同時價格也會更貴。收發器需要統一購買和安裝，所以全部哨所只能選擇安裝一種型號的收發器。換句話說，每一對哨所之間的通話距離都是同一個 D。你的任務是確定收發器必須的最小通話距離 D，使得每一對哨所之間至少有一條通話路徑（直接的或者間接的）。

題解

#include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std;const int MAX_NODE = 510, MAX_EDGE = MAX_NODE * MAX_NODE;struct Node {int X, Y;Node *Father; }_nodes[MAX_NODE]; int TotNode, S;struct Edge {Node *From, *To;double Weight;bool operator < (const Edge& a) const{return Weight < a.Weight;} }_edges[MAX_EDGE]; int _eCount;double Dist(Node& a, Node& b) {int dx = a.X - b.X, dy = a.Y - b.Y;return sqrt(dx * dx + dy * dy); }Node *FindRoot(Node *cur) {return cur->Father == cur ? cur : cur->Father = FindRoot(cur->Father); }double Kruskal() {for (int i = 1; i <= TotNode; i++)_nodes[i].Father = _nodes + i;sort(_edges + 1, _edges + _eCount + 1);int cnt = 0;for (int i = 1; i <= _eCount; i++){Edge *e = _edges + i;Node *root1 = FindRoot(e->From), *root2 = FindRoot(e->To);if (root1 != root2){root1->Father = root2;cnt++;if (cnt == TotNode - S)return e->Weight;}}return -1; }int main() {scanf("%d%d", &S, &TotNode);for (int i = 1; i <= TotNode; i++)scanf("%d%d", &_nodes[i].X, &_nodes[i].Y);for (int i = 1; i <= TotNode; i++)for (int j = i + 1; j <= TotNode; j++){Edge *e = _edges + ++_eCount;e->From = _nodes + i;e->To = _nodes + j;e->Weight = Dist(_nodes[i], _nodes[j]);}printf("%.2f\n", Kruskal());return 0; }

　　

轉載于:https://www.cnblogs.com/headboy2002/p/9463207.html

總結

以上是生活随笔為你收集整理的luogu1991 无线通讯网的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。