傳送門

求一棵最小生成樹，要求：忽略樹上s-1條邊的邊權后，最大的邊最小。

（因為衛星頻道是兩兩互達的，所以想把連接兩個聯通塊之間的邊權忽略必須用兩個聯通塊都放置衛星頻道。也就是至少要兩個）

emmm...其實我本來想的是分層最短路那種動態規劃，記錄用了幾次忽略機會。

假設已經求出答案最小生成樹，忽略邊權一定是忽略前s-1大的，那么所求即為第s大的邊權。

考慮kruskal算法求最小生成樹，每次都選最小的邊加入...這樣其實就保證了每條邊都是當前最小的，那第s大一定也是最小的。

證明？在一棵最小生成樹上，用一條非樹邊代替樹邊，那么第s大的邊的邊權要么不變要么變大。（來自學姐）

其實就是裸的最小生成樹啊w

代碼如下

?

#include<cstdio> #include<iostream> #include<cmath> #include<cstring> #define MogeKo qwq #include<algorithm> using namespace std; const int maxn = 1e6; int t,s,n,cnt,num; int px[maxn],py[maxn],fa[maxn];struct node {int from,to;double val;bool operator < (const node & N) const {return val < N.val;} } e[maxn];void add(int a,int b) {e[++cnt].from = a;e[cnt].to = b;e[cnt].val = sqrt( pow(px[a]-px[b],2) + pow(py[a]-py[b],2) ); }int getfa(int x) {if(fa[x] == x)return x;else return fa[x] = getfa(fa[x]); }double kruskal() {for(int i = 1; i <= cnt; i++) {int x = getfa(e[i].from);int y = getfa(e[i].to);if(x == y)continue;fa[x] = y;num++;if(num == n-s)return e[i].val;} }int main() {scanf("%d",&t);while(t--) {scanf("%d%d",&s,&n);cnt = num = 0;for(int i = 1; i <= n; i++)fa[i] = i;for(int i = 1; i <= n; i++)scanf("%d%d",&px[i],&py[i]);for(int i = 1; i <= n; i++)for(int j = i+1; j <= n; j++)add(i,j);sort(e+1,e+cnt+1);printf("%.2lf\n",kruskal());}return 0; } View Code

?

轉載于:https://www.cnblogs.com/mogeko/p/10914238.html

總結

以上是生活随笔為你收集整理的UVA10369 Arctic Network的全部內容，希望文章能夠幫你解決所遇到的問題。

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