这道题很显然能够看出，只需找出与卫星电话数相等的联通块数，然后取联通块里的最大边就可以了。但是我想不出来怎么好写。
看过题解之后，经题解提醒“树的性质：删掉n条边一定出现n+1个连通块”，这样就好做了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 | #include<iostream> #include<cmath> #include<algorithm> #include<queue> #define ll long long #define pii pair<int,int> #define PINF 0x7fffffff #define NINF 0x80000000 using namespace std; int s, p; struct edge { int u, v; double w; bool operator < (const edge& e2) const { return w < e2.w; } }edges[125000]; struct point { int x, y; }points[505]; int father[505]; int _find(int x) { if (father[x] == 0)return x; return father[x] = _find(father[x]); } bool _union(int x, int y) { x = _find(x); y = _find(y); if (x == y)return false; father[x] = y; return true; } inline double dis(int x1, int y1, int x2, int y2) { return sqrt((double)((x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2))); } int main() { //ios::sync_with_stdio(false); cin >> s >> p; for (int i = 1; i <= p; i++) { cin >> points[i].x >> points[i].y; } int ePtr = 0; for (int i = 1; i <= p; i++) { for (int j = i + 1; j <= p; j++) { ePtr++; edges[ePtr].u = i; edges[ePtr].v = j; edges[ePtr].w = dis(points[i].x, points[i].y, points[j].x, points[j].y); } } sort(edges + 1, edges + ePtr + 1); int cnter = 0; for (int i = 1; i <= ePtr; i++) { if (_union(edges[i].u, edges[i].v)) { cnter++; } if (cnter == p - 1 - (s - 1)) { printf("%.2lf", edges[i].w); break; } } } |