北极通讯网络

solution

题目很抽象，简化一下就是求解一个最小的 $dd$ ，使得删去权值大于 $dd$ 的边后，剩下的联通块的个数不超过 $kk$ 个。可发现本题难点就在于模型的抽象，抽象出这一点来，解题不难。我们在进行 $KruskalKruskal$ 算法时其实就是在维护图中联通块的个数。在每次和合并并差集的时候联通块的数量减一。所以我们只需要在求解 $MSTMST$ 的过程中记录一下合并的次数即可，当合并次数恰好为 $n-kn-k$ 时，此时加入的树边的权值就为 $dd$ 。

code

#include <bits/stdc++.h>
#define mk make_pair
#define x first
#define y second 
#define pii pair<int , i >
using namespace std ;
const int maxn = 1e5 + 7 ;
int n , m , cnt ; 
pii q[maxn] ;
struct node 
{
    int frm , to ;
    double dis ;
}  ed[maxn << 1] ;
bool operator <(node a , node b )
{
	return a.dis < b.dis ;
}
int fa[maxn] ; 
int find(int a)
{
    if(fa[a] == a)  return a ;
    return fa[a] = find(fa[a]) ;
}
void add(int u , int v , int w)
{
    ed[++cnt] = {u , v , w } ; 
}
double len(pii a , pii b)
{
    int x1 = a.x , x2 = b.x , y1 = a.y , y2 = b.y ; 
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)) ;  
}
signed main()
{
    cin >> n >> m ;
    for(int i = 1 ; i <= n ; i++ )
	{
	   cin >> q[i].x >> q[i].y ; 
	   fa[i] = i ; 
	}
    for(int i = 1 ; i <= n ; i++ )  
        for(int j = i + 1 ; j <= n ; j++ )
            add(i , j , len(q[i] , q[j])) ; 
    sort(ed , ed + cnt + 1) ; 
    int tot = n ;   double res = 0 ;
    for(int i = 1 ; i <= cnt ; i++ )
    {
        if( tot <= m)    break ;
        int u = find(ed[i].frm) , v = find(ed[i].to) ; 
        if(u == v)  continue ;
        tot-- , res = ed[i].dis ;   fa[v] = u ; 
    }
    printf("%.2lf" , res) ;
    return 0 ; 
}