題目鏈接請戳 這里

?

解題思路

最小生成樹。用Kruskal得到最小生成樹。

再用貪心，最長的那些邊連電纜，剩余的用電報，

這樣就很容易想到半徑是多少。

?

代碼

#include<stdio.h> #include<string.h> #include<algorithm> #include<math.h> #define N 510 using namespace std;struct point {int x, y; }p[N]; struct edge {int u, v;double w; }e[N*N]; int set[N]; int d[N*N]; int n, m, en;int cmp(const int i, const int j) {return e[i].w < e[j].w; }double path(int i, int j) {return sqrt(pow(p[i].x - p[j].x, 2) + pow(p[i].y - p[j].y, 2)); }void make_set() {for(int i = 1; i <= n; i++)set[i] = i; }int find(int x) {return x == set[x] ? x : set[x] = find(set[x]); }double Kruskal(int s) {int t = 0;for(int i = 0; i < en; i++) d[i] = i;make_set();sort(d, d + en, cmp);for(int i = 0; i < en; i++) {int c = d[i];int pa = find(e[c].u);int pb = find(e[c].v);if(pa != pb) {t++;set[pa] = pb;if(t == s) return e[c].w;}} }int main() {int tests;scanf("%d", &tests);while(tests--) {scanf("%d%d", &m, &n);for(int i = 1; i <= n; i++) {scanf("%d%d", &p[i].x, &p[i].y);}en = 0;for(int i = 1; i <= n; i++) {for(int j = 1; j <= n; j++) if(i != j) {e[en].u = i; e[en].v = j;e[en].w = path(i, j);en++;}}double ans = Kruskal(n - m);printf("%.2lf\n", ans);}return 0; }

?

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

總結(jié)

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

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