克鲁斯卡尔算法的扩展应用
题目讲的有点抽象.
我们抽象一下题目,发现题目是在求这样一个东西:
我们需要找到一个最小的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;
}
}
}
老哥,你还要加一个k>=n的特判,不然过不去
老哥,cnt不是应该等于 k-1吗
老哥,那你得看
cnt
是什么了如果cnt是删去的边的条数那么cnt就是k-1 但是在这里的cnt是剩下的边 也就是加入的边 原来的树边数=n-1 要删去k-1条边 那么就剩下 n-1-(k-1)=n-k