头像

yingzhaoyang


访客:8350

离线:2个月前



yingzhaoyang
6个月前

Tarjan算法求强联通分量

强联通分量模板题.
当然,你需要知道什么是强联通分量,以及怎么求强联通分量

先用Tarjan算法求强联通分量.
再记录新图上每个点的出度,再找出初度为0的点,如果只有一个,直接加上该强联通分量的大小.
大于一的话答案即为0.

时间复杂度 $O(n+m)$

C++ 代码

//#pragma GCC optimize(3,"inline","Ofast","fast-math","no-stack-protector","unroll-loops")
//#pragma GCC target("sse","sse2","sse3","sse4","avx","avx2","popcnt")
//相信奇迹的人,本身就和奇迹一样了不起.
#include<bits/stdc++.h>
#define N 10010
#define M 50010
using namespace std;
struct node{
    int to,next;
}e[M];
stack<int> s;
vector<int> scc[N];
int tot,head[N];
int n,m,cnt,num;
int dfn[N],low[N],id[N],dout[N];
bool ins[N];
inline void add(int u,int v)
{
    tot++;
    e[tot].to=v;
    e[tot].next=head[u];
    head[u]=tot;
}
void tarjan(int u)
{
    dfn[u]=low[u]=++num;
    s.push(u),ins[u]=1;
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(ins[v])
            low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]){
        cnt++;
        int v;
        do{
            v=s.top(),s.pop();
            ins[v]=0;
            id[v]=cnt,scc[cnt].push_back(v);
        }while(v!=u);
    }
}
int main()
{
    //freopen(".in","r",stdin),freopen(".out","w",stdout);
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d %d",&u,&v);
        add(u,v);
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i])
            tarjan(i);
    for(int u=1;u<=n;u++)
        for(int i=head[u];i;i=e[i].next){
            int v=e[i].to;
            if(id[u]!=id[v])
                dout[id[u]]++;
        }
    int zeros=0,ans=0;
    for(int i=1;i<=cnt;i++)
        if(!dout[i]){
            zeros++;
            ans+=scc[i].size();
            if(zeros>1){
                ans=0;
                break;
            }
        }
    printf("%d\n",ans);
    return 0;
}
/*
*
*  ┏┓   ┏┓+ +
* ┏┛┻━━━┛┻┓ + +
* ┃       ┃
* ┃   ━   ┃ ++ + + +
*  ████━████+
*  ◥██◤ ◥██◤ +
* ┃   ┻   ┃
* ┃       ┃ + +
* ┗━┓   ┏━┛
*   ┃   ┃ + + + +Code is far away from  
*   ┃   ┃ + bug with the animal protecting
*   ┃    ┗━━━┓ 神兽保佑,代码无bug 
*   ┃        ┣┓
*    ┃        ┏┛
*     ┗┓┓┏━┳┓┏┛ + + + +
*    ┃┫┫ ┃┫┫
*    ┗┻┛ ┗┻┛+ + + +
*/



yingzhaoyang
6个月前

题目描述

题意:求不定方程$\frac{1}{x}+\frac{1}{y}=\frac{1}{n!}$的正整数解的个数.
($x$,$y$为未知数,$n$为给定的数)

样例

输入样例: 1439 

输出样例: 102426508

线性筛素数(主要算法:数学推导)

下面是玄学数学推导时间:

因为
$$\frac{1}{x}+\frac{1}{y}=\frac{1}{n!}$$
可以很轻松地看出 $\frac{1}{x}$和$\frac{1}{y}$是小于$\frac{1}{n!}$的,于是由小学知识可知$x$和$y$是大于$n!$的.

于是,我们令
$$y=n!+k (k\in {N*})$$

于是,原式变为
$$\frac{1}{x}+\frac{1}{n!+k}=\frac{1}{n!}$$

两边通分,得
$$n! \times (n!+k)+x \times n!=x \times (n!+k)$$

整理,得
$$x=\frac{(n!)^{2}}{k}+k$$

分析至此,已经比较明晰了.

因为$x$是正整数,则$\frac{(n!)^{2}}{k}+k$也必须为正整数.

又因为$k\in{N*}$,故只需$\frac{(n!)^{2}}{k}$为正整数即可.

由于$k$可以为任意正整数,故$k$只需取$(n!)^{2}$的约数即可.

此时$x=\frac{(n!)^{2}}{k}+k$为正整数,$y=n!+k$也为正整数,故这样的$k$是满足题意的.

所以本题的实质其实是:
$$求(n!)^{2}的正约数个数和$$

玄学数学推导终于结束了…

接下来才是真正与算法有关的部分了.
我们知道,一个正整数可以被唯一分解为
$$N=p_1^{c_1} \cdot p_2^{c_2} \cdot p_3^{c_3} \cdots p_m^{c_m}$$

其中$c_i$均为正整数,$p_i$均为质数,且满足$p_1<p_2<p_3< \cdots <p_m$

则$N$的正约数个数为
$$(c_1+1) \cdot (c_2+1) \cdot (c_3+1) \cdot \cdots \cdot(c_m+1) = \prod_{i=1}^m (c_i+1)$$

所以我们只需找出所有的$c_i$即可.

为了提高效率,我们采用线性筛素数的方法,先找出$n!$的质因子,再通过分解质因数的方法找出所有的$c_i$即可.

注意我们这里只是找出了$n!$的所有的$c_i$,而题目要求的是$(n!)^{2}$的约数个数,所以统计时一定要乘2!!!!

因为平方过后,$n!$的所有$c_i$都变为了$2c_i$.(这个应该可以理解吧....)

还有一件事,记得取模(此事非常重要)!!!!

自此,你就完美的解决了这道题.

时间复杂度 $O(nlogn)$

C++ 代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll MAX=1e6+1;
const ll mod=1e9+7;
ll n,ans=1;
ll c[MAX],prime[MAX];//c[i]为指数 
ll flag[MAX],s[MAX];
int tot;
inline void Linear()//线性筛素数 (查找1到n中每个数的最小质因子并记录位置)
{
    for(int i=2;i<=n;i++){
        if(!flag[i]){
            prime[++tot]=i;
            s[i]=tot;   
        }
        for(int j=1;j<=tot&&i*prime[j]<=n;j++){
            flag[i*prime[j]]=1;
            s[i*prime[j]]=j;// s[i] 表示 i 的最小质因子在prime数组中的位置 
            if(i%prime[j]==0)
                break;
        }
    }
}
inline void divide(int x)//将x分解质因数 
{
    while(x!=1){
        ++c[s[x]];//s[x]为x的最小质因子,c[s[x]]表示s[x]这个质因子的指数 
        x/=prime[s[x]];//分解 
    }
}
int main()
{
    scanf("%lld",&n);
    Linear();
    for(int i=1;i<=n;i++)
        divide(i);
    for(int i=1;i<=MAX;i++)
        if(c[i])
            ans=ans*(2*c[i]+1)%mod;//注意这里要乘二,因为最后统计的是n!的约数个数,而不是n!,所以所有的ci要变为2*ci
    printf("%lld\n",ans);
    return 0;
}
/*
*
*  ┏┓   ┏┓+ +
* ┏┛┻━━━┛┻┓ + +
* ┃       ┃
* ┃   ━   ┃ ++ + + +
*  ████━████+
*  ◥██◤ ◥██◤ +
* ┃   ┻   ┃
* ┃       ┃ + +
* ┗━┓   ┏━┛
*   ┃   ┃ + + + +Code is far away from  
*   ┃   ┃ + bug with the animal protecting
*   ┃    ┗━━━┓ 神兽保佑,代码无bug 
*   ┃        ┣┓
*    ┃        ┏┛
*     ┗┓┓┏━┳┓┏┛ + + + +
*    ┃┫┫ ┃┫┫
*    ┗┻┛ ┗┻┛+ + + +
*/



yingzhaoyang
7个月前

KMP子符串匹配

代码里已经码的比较清楚了.....

时间复杂度 $O(n)$

C++ 代码

#include<bits/stdc++.h>
#define N 1000010
#define ll long long
#define next _next
using namespace std;
/*
    显然当时考试的时候没有考虑到如果是1e6个a,暴力往回跳是会超时的...(递归过深)
    经过分析我们发现,如果不考虑重叠的情况,那此时的num数组是可以直接递推求出.
    因为一个子串的所有相同的前后缀可以表示为{next[i],next[next[i]],next[next[next[i]]]....}.
    一个显而易见的结论就是num[i]=num[next[i]]+1.(不考虑重叠的情况) 
    然后考虑去重.
    我们都知道next[i]一定小于i.
    那么如果我们已经从i这个位置往回跳next,跳了若干次后,发现此时的next小于了i的一半,那这个next
    就是我们要的不重叠的总数,即num[i]=此时的next.
    当然,我们还是遇到这个问题,如果来1e6个a,还是会面临超时.
    考虑优化,其实我们需要优化的核心是减少递归次数.
    我们就再求一遍next数组,在求时,顺带递归,如果当前的j满足小于i的一半,那这就是当前的答案. 
*/
const ll mod=1e9+7;
char str[N];
int len,n,next[N];
ll num[N],ans;
inline void solve()
{
    len=strlen(str+1);
    int k=0;
    next[1]=0,num[1]=1;
    for(int i=2;i<=len;i++){
        while(k&&(str[k+1]!=str[i]))
            k=next[k];
        if(str[k+1]==str[i])
            k++;
        next[i]=k;
        num[i]=num[k]+1;
        //num数组是可以直接递推求出(注意此时的num数组还未去除含有重叠公共前后缀的数目) 
    }
    k=0;
    for(int i=2;i<=len;i++){
        while(k&&(str[k+1]!=str[i]))
            k=next[k];
        if(str[k+1]==str[i])
            k++;
        while(k*2>i&&next[k])
            k=next[k];
        ans=(ans*(ll)(num[k]+1))%mod;
    }
}
int main()
{
//  freopen("zoo.in","r",stdin);
//  freopen("zoo.out","w",stdout);
    scanf("%d",&n);
    while(n--){
        ans=1;
        memset(next,0,sizeof(next));
        memset(num,0,sizeof(num));
        scanf("%s",str+1);
        solve();
        printf("%lld\n",ans);
    }
    return 0;
} 



yingzhaoyang
7个月前

最小生成树

其实这道题完全是一道水题,像我这样随便乱搞都可以过....
刚看到这道题,我就意识到他绝对与最小生成树有关.
于是直接上了模板,万万没想到,他过了.....

时间复杂度 $O(nlogn)$

C++ 代码

//相信奇迹的人,本身就和奇迹一样了不起.
#include<bits/stdc++.h>
#define N 20
using namespace std;
struct node{
    int from,to,dis;
}e[N*N];
int n,m,v[N],in[N];//in数组记录有几条边与该点有关,方便判联通
int fa[N],tot,cnt;
bool rule(const node &a,const node &b)//按边权从小到大排序
{
    return a.dis<b.dis;
}
int find(int x)//路径压缩
{
    if(fa[x]==x)
        return fa[x];
    return fa[x]=find(fa[x]);
}
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++){
        fa[i]=i;
        scanf("%d",&v[i]);
    }
    for(int i=1;i<=m;i++){
        scanf("%d %d %d",&e[i].from,&e[i].to,&e[i].dis);
        e[i].from++,e[i].to++;
        in[e[i].from]++,in[e[i].to]++;
    }
    for(int i=1;i<=n;i++)
        if(!in[i]&&v[i]){//如果没有一条边与这个点有关,且这个点的v[i]不为0,表明这个点永远不可能与其他点能量一 //样,直接输出Impossible
            puts("Impossible");
            return 0;
        }
    sort(e+1,e+1+m,rule);
    for(int i=1;i<=m;i++){//克鲁斯卡尔算法求最小生成树
        if(tot==n-1)
            break;
        int u=e[i].from,v=e[i].to;
        if(find(u)!=find(v)){
            fa[find(v)]=find(u);
            cnt+=e[i].dis;
            tot++;
        }
    }
    printf("%d\n",cnt);
    return 0;
}



yingzhaoyang
8个月前
差分约束

这题没什么好说的.
可以很快的看出是差分约束的模板题.
当然,如果不知道什么是差分约束,建议去看一下yxc大佬的讲解.
差分约束最主要是要搞清建边的方向.
还有这道题由于问的是最小值,要求最长路.
另外,对于此题而言,十年oi一场,不开long long见祖宗.
在此不得不说句话:stack大法好啊!

时间复杂度 $SPFA玄学复杂度$

C++ 代码

#include<bits/stdc++.h>
#define N 100010
#define M 300010
#define ll long long
using namespace std;
struct node{
    int to,d,next;
}e[M];
int tot,head[N];
int n,k,dis[N],cnt[N];
bool vis[N];
inline void add(int u,int v,int d)//加边什么的都是老套路了
{
    tot++;
    e[tot].to=v;
    e[tot].d=d;
    e[tot].next=head[u];
    head[u]=tot;
}
inline bool SPFA()//SPFA模板
{
    memset(dis,-0x3f,sizeof(dis));
    stack<int> q;
    q.push(0),dis[0]=0,vis[0]=1;
    while(!q.empty()){
        int now=q.top();
        q.pop();
        vis[now]=0;
        for(int i=head[now];i;i=e[i].next){
            int v=e[i].to;
            if(dis[v]<dis[now]+e[i].d){
                dis[v]=dis[now]+e[i].d;
                cnt[v]=cnt[now]+1;
                if(cnt[v]>=n+1)//注意判负环
                    return 0;
                if(!vis[v])
                    q.push(v),vis[v]=1;
            }
        }
    }
    return 1;
}
int main()
{
    scanf("%d %d",&n,&k);
    for(int i=1;i<=k;i++){
        int x,u,v;
        scanf("%d %d %d",&x,&u,&v);
        //分五种情况建边,注意方向
        if(x==1)
            add(v,u,0),add(u,v,0);
        if(x==2)
            add(u,v,1);
        if(x==3)
            add(v,u,0);
        if(x==4)
            add(v,u,1);
        if(x==5)
            add(u,v,0);
    }
    for(int i=1;i<=n;i++)
        add(0,i,1);
    if(!SPFA())
        puts("-1");
    else{
        ll res=0;
        for(int i=1;i<=n;i++)
            res+=dis[i];
        printf("%lld\n",res);
    }
    return 0;
}



yingzhaoyang
8个月前

区间DP+高精度

不得不说于高精度挂钩的题目都比较毒瘤....

对于这道题,首先可以发现对于每一行的取法对其他行是没有影响的.
于是我们就可以单独考虑每一行,让每一行取到最大值,在总体求和即可.

于是我们设dp[i][j]表示当前区间为[i,j]的最大分数.
由于每一次都只在该行的行首和行尾取数,于是[i,j]可以从[i-1,j]或[i,j+1]转移过来.
于是就有dp[i][j]=max(dp[i-1][j]+Map[i-1]2^(m+i-j-1),dp[i][j+1]+Map[j+1]2^(m+i-j-1));
其中Map[i]代表该行的第i个数.

然后就要考虑毒瘤高精度运算,自然是套模板呀....
这题竟然还要用压位高精

时间复杂度 $O(nm^2)$

C++ 代码

//相信奇迹的人,本身就和奇迹一样了不起.
#include<bits/stdc++.h>
#define SIZE 1010
#define N 85
using namespace std;
const int mod=1e4;//压四位即可
struct hugeint{
    int num[SIZE],len;
}dp[N][N],power_2[N],ans;
int n,m,Map[N];
hugeint max (const hugeint &a,const hugeint &b){//比较函数
        if(a.len>b.len)
            return a;
        if(a.len<b.len)
            return b;
        for(int i=a.len;i>=1;i--){
            if(a.num[i]>b.num[i])
                return a;
            if(a.num[i]<b.num[i])
                return b;
        }
        return a;
    }
hugeint operator + (const hugeint &a,const hugeint &b){//高精加
    hugeint c;
    memset(c.num,0,sizeof(c.num));
    c.len=max(a.len,b.len);
    for(int i=1;i<=c.len;i++){
        c.num[i]+=(a.num[i]+b.num[i]);
        c.num[i+1]+=c.num[i]/mod;
        c.num[i]%=mod;
    }
    if(c.num[c.len+1])
        c.len++;
    return c;
}
hugeint operator * (const hugeint &a,const int &b){//高精乘
    hugeint c;
    memset(c.num,0,sizeof(c.num));
    c.len=a.len;
    int temp=0;
    for(int i=1;i<=c.len;i++){
        c.num[i]=(a.num[i]*b+temp);
        temp=c.num[i]/mod;
        c.num[i]%=mod;
    }
    while(temp){
        c.num[++c.len]=temp%mod;
        temp/=mod;
    }
    return c;
}
inline void init()//预处理2的幂次
{
    power_2[0].num[1]=1,power_2[0].len=1;
    for(int i=1;i<=m+2;i++)
        power_2[i]=power_2[i-1]*2;
}
inline void print(hugeint a)//输出
{
    printf("%d",a.num[a.len]);
    for(int i=a.len-1;i>=1;i--){//压位的输出有讲究
        if(!a.num[i]){
            printf("0000");
            continue;
        }
        for(int j=10;j*a.num[i]<mod;j*=10)
            printf("0");
        printf("%d",a.num[i]);
    }
    printf("\n");
}
int main()
{
    //freopen("game.in","r",stdin),freopen("game.out","w",stdout);
    scanf("%d %d",&n,&m);
    init();
    while(n--){//处理每一行
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=m;i++)
            scanf("%d",&Map[i]);
        for(int i=1;i<=m;i++)
            for(int j=m;j>=i;j--){//注意从大区间dp到小区间
                dp[i][j]=max(dp[i][j],dp[i-1][j]+power_2[m+i-j-1]*Map[i-1]);
                dp[i][j]=max(dp[i][j],dp[i][j+1]+power_2[m+i-j-1]*Map[j+1]);
            }
        hugeint MAX;
        memset(MAX.num,0,sizeof(MAX.num));
        MAX.len=0;
        for(int i=1;i<=m;i++)//因为每一个数都可能成为最后取的数,所以要循环找最大的
            MAX=max(MAX,dp[i][i]+power_2[m]*Map[i]);
        ans=ans+MAX;//累加答案
    }
    print(ans);
    return 0;
}



yingzhaoyang
8个月前

字符串哈希+二分

抽象一下题目,其实题目就是要让你求在a串中有多少个位置i,
使得a[i..n]和b[1..m]的最长公共前缀的长度恰好为x(注意是恰好,不能多,也不能少).

听说正解是扩展KMP....
但我不会呀!!!

于是上字符串哈希吧…
先预处理出k的幂次,a串的哈希值,b串的哈希值.
然后我们就要考虑如何求出a[i..n]和b[1..m]的最长公共前缀的长度.

枚举长度,计算哈希值???
明显会超时.

观察一下数据范围,n,m,q<=200000,感觉是个$nlogn$的算法.
这不就是二分吗!!!!
直接二分最长匹配长度,计算哈希值即可.

时间复杂度 $O(nlogn)$

C++ 代码

//相信奇迹的人,本身就和奇迹一样了不起.
#include<bits/stdc++.h>
#define N 200010
#define ll long long
using namespace std;
const ll k=131;
int n,m,q;
ll Hash_a[N],Hash_b[N],power_k[N];
ll cnt[N];
char a[N],b[N];
inline void init()//预处理k的幂次,a串的哈希值,b串的哈希值
{
    power_k[0]=1;
    for(int i=1;i<=max(n,m);i++) 
        power_k[i]=(power_k[i-1]*k);
    for(int i=1;i<=n;i++) 
        Hash_a[i]=(Hash_a[i-1]*k+a[i]);
    for(int i=1;i<=m;i++) 
        Hash_b[i]=(Hash_b[i-1]*k+b[i]);
}
inline ll get_Hash_a(int x,int y){//求a的子串a[x..y]的哈希值
    return Hash_a[y]-Hash_a[x-1]*power_k[y-x+1];
}
inline ll get_Hash_b(int x,int y){//求b的子串b[x..y]的哈希值
    return Hash_b[y]-Hash_b[x-1]*power_k[y-x+1];
}
int main()
{

    scanf("%d %d %d",&n,&m,&q);
    scanf("%s",a+1);
    scanf("%s",b+1);
    init();
    for(int i=1;i<=n;i++){
        if(a[i]!=b[1]){//如果第一个字符都不匹配,则最大匹配长度为0
            cnt[0]++;
            continue;
        }
        int l=1,r=min(m,n+1-i);
        while(l<r){//寻找最大匹配长度
            int mid=(l+r+1)>>1;
            if(get_Hash_b(1,mid)==get_Hash_a(i,i+mid-1))//如果当前可以匹配,向上缩短下界
                l=mid;
            else //否则向下缩短上界
                r=mid-1;
        }
        cnt[r]++;//当前长度的匹配位置+1
    }
     while(q--){
        int x;
        scanf("%d",&x);
        printf("%lld\n",cnt[x]);
    }
    return 0;
}



yingzhaoyang
8个月前

任何一个伟大的思想,都有一个微不足道的开始.

C++经典入门题.

C++ 代码

#include<bits/stdc++.h>
int mian()
{
    int a,b;
    scanf("%d %d",&a,&b);
    printf("%d\n",a+b);
    return 0;
}



yingzhaoyang
8个月前

最小生成树的扩展应用

对于这道题,我们可以假设一个虚拟的”超级发电站”.
而在每一个矿井修建发电站就相当于是从超级发电站向其连一条权值为v[i]的边.
之后我们惊奇的发现这就是一道最小生成树的模板题.
直接上克鲁斯卡尔算法即可..

时间复杂度 $O(nlogn)$

C++ 代码

#include<bits/stdc++.h>
#define N 310
using namespace std;
struct node{
    int from,to,dis;
}e[N*N];
int n,v,p[N][N];
int fa[N],tot,cnt,ans;
bool rule(const node &x,const node &y)//按边权从小到大排序
{
    return x.dis<y.dis;
}
int find(int x)//并查集基本操作
{
    if(fa[x]==x)
        return x;
    return fa[x]=find(fa[x]);
}
inline void merge(int x,int y)//并查集基本操作
{
    fa[find(y)]=find(x);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n+1;i++)//并查集初始化
        fa[i]=i;
    for(int i=1;i<=n;i++){
        scanf("%d",&v);
        e[++tot].from=n+1;//从"超级发电站"向该点连一条权值为v的边
        e[tot].to=i;
        e[tot].dis=v;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&p[i][j]);
    for(int i=1;i<n;i++)
        for(int j=i+1;j<=n;j++){
            e[++tot].from=i;
            e[tot].to=j;
            e[tot].dis=p[i][j];
        }
    sort(e+1,e+1+tot,rule);
    for(int i=1;i<=tot;i++){//标准克鲁斯卡尔算法
        int u=e[i].from,v=e[i].to;
        if(find(u)!=find(v)){
            merge(u,v);
            ans+=e[i].dis;
        }
    }
    printf("%d\n",ans);
    return 0;
}



yingzhaoyang
8个月前

克鲁斯卡尔算法的扩展应用

题目讲的有点抽象.
我们抽象一下题目,发现题目是在求这样一个东西:

我们需要找到一个最小的d值,使得在删去权值大于d的所有边后,
剩下的联通块个数不超过k.

抽象完题目后,我们会发现一个事实:

随着d的值不断增大,所能形成的联通块数量会逐渐减小.
这是一个显然的结论

一看到联通块,我们可以快速的想到克鲁斯卡尔算法.
回忆克鲁斯卡尔算法的过程:
1.将边权从小到大排序.
2.依次从小到大扫描每一条边,合并没有合并的点集.

我们发现第二步本质上就是在维护联通快的个数.
由此我们就得到了这道题的解决方法:
正常执行克鲁斯卡尔算法,记录当前已经加入了几条边.
当加入某条边后,恰好加入了n-k条边.
那么这条边的权值就是最终答案.

时间复杂度 $O(nlogn)$

C++ 代码

//#pragma GCC optimize(3,"inline","Ofast","fast-math","no-stack-protector","unroll-loops")
//#pragma GCC target("sse","sse2","sse3","sse4","avx","avx2","popcnt")
//相信奇迹的人,本身就和奇迹一样了不起.
#include<bits/stdc++.h>
#define N 510
#define INF 0x7fffffff
#define ll long long
using namespace std;
struct Node{
    int x,y;
}p[N];
struct node{
    int from,to;
    double dis;
}e[N*N];
int n,k;
int fa[N];
int cnt,tot;
inline double path(int x1,int y1,int x2,int y2)//计算距离
{
    return sqrt(pow((x1-x2),2)+pow((y1-y2),2));
}
inline void add(int u,int v)//加边
{
    tot++;
    e[tot].from=u;
    e[tot].to=v;
    e[tot].dis=path(p[u].x,p[u].y,p[v].x,p[v].y);
}
int find(int x)//并查集基本操作
{
    if(fa[x]==x)
        return x;
    return fa[x]=find(fa[x]);
}
inline void merge(int x,int y)//并查集基本操作
{
    fa[find(y)]=find(x);
}
bool rule(const node &x,const node &y)//按边权从小到大排序
{
    return x.dis<y.dis;
}
int main()
{
    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d %d",&p[i].x,&p[i].y);
        fa[i]=i;//并查集初始化
    }
    for(int i=1;i<n;i++)
        for(int j=i+1;j<=n;j++)
            add(i,j);
    sort(e+1,e+1+tot,rule);
    for(int i=1;i<=tot;i++){
        int u=e[i].from,v=e[i].to;
        if(find(u)!=find(v)){
            merge(u,v);//合并点集
            cnt++;
        }
        if(cnt==n-k){//已经加入了n-k条边
            printf("%.2lf\n",e[i].dis);//输出结果
            return 0;
        }
    }
}