养成先点赞后阅读的好习惯
逃
题目描述
这道题用贪心的思想想一下
就是叫我们先跑一遍最小生成树,然后再删除前k大的边,再输出最大的那条边。(蒟蒻一枚,勿喷)
最小生成树
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=555;
template<class T>void read(T &x)//快读
{
x=0;bool f=0;char ch=getchar();
while(ch<'0'||ch>'9') {f|=(ch=='-');ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
x=f?-x:x;
return;
}
struct stt
{
int x,y;
}a[555];
struct st
{
int s,e;
double d;
}b[555*400];
bool cap(st a,st b)
{
return a.d<b.d;
}
double js(stt a,stt b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}//求距离
int f[N];
int n,k;
int cnt;//记录共有多少条边
int get(int x)
{
if(x==f[x]) return x;
return f[x]=get(f[x]);
}
int nn;
int main()
{
read(n),read(k);
for(int i=1;i<=n;i++)
read(a[i].x),read(a[i].y),f[i]=i;
for(int i=1;i<n;i++)
for(int j=i+1;j<=n;j++)
b[++cnt].s=i,b[cnt].e=j,b[cnt].d=js(a[i],a[j]);//加入每条边
//Kruskal算法
sort(b+1,b+cnt+1,cap);
for(int i=1;i<=cnt;i++)
{
int a=get(b[i].s),bbb=get(b[i].e);
if(a==bbb) continue;
nn++;//记录已经加入了多少边
f[a]=bbb;
if(nn==n-k)//还剩k条边,即这条边是第k+1大的
{
printf("%.2lf",b[i].d);
return 0;
}
}
return 0;
}
您的代码现在测试样例也输出不出结果了……
贴一个我的吧,思路和作者一样,但刚开始没过,看了作者的代码知道确实是能过,改了改就过了。注意要先判断生成树的边数和最多需要多少条边的关系,否则会导致出错,体现在贴主的代码上就是输出不了。
为什么二分+并查集要比kruskal慢很多?
代码发一下呗
#include [HTML_REMOVED]//二分+并查集
#include [HTML_REMOVED]
#include [HTML_REMOVED]
#include [HTML_REMOVED]
#include [HTML_REMOVED]
#define x first
#define y second
using namespace std;
typedef pair[HTML_REMOVED] PII;
const int N = 510;
int n, k, fa[N];
PII p[N];
double dist(const PII& a, const PII& b)
{
int dx = a.x - b.x, dy = a.y - b.y;
return sqrt(1.0 * dx * dx + dy * dy);
}
int get(int x)
{
if (fa[x] == x) return x;
return fa[x] = get(fa[x]);
}
bool check(double x)
{
for (int i = 1; i <= n; i ) fa[i] = i;
int cnt = n;
for (int i = 1; i <= n; i )
for (int j = 1; j < i; j ++ )
if (dist(p[i], p[j]) <= x)
{
int a = get(i), b = get(j);
if (a != b) fa[a] = b, cnt – ;
}
return cnt <= k || cnt == 1;
}
int main()
{
scanf(“%d%d”, &n, &k);
for (int i = 1; i <= n; i ++ ) scanf(“%d%d”, &p[i].x, &p[i].y);
}
你这二分时间复杂度多了一个 log呀
..........数据更新之后,直接卡麻了
https://www.acwing.com/file_system/file/content/whole/index/content/5882129/
帮我看代码
他的代码也有问题
我的代码有点问题,能问问嘛
大佬这个是不是有问题,有可能最大的两条边是四个不同的顶点,需要四个卫星设备
呃,实际上是不用的,只需要三个就够了,你自己画图看一下就知道了,这样的四个顶点,必然有两个已经在一个连通块内了,你不需要他俩放两个卫星设备,放一个就可以了
这个为什么考虑的是第k大边的问题呢,一条路径上最多需要两个卫星,最少也要1个,那么也不会是第k大把?
老哥,不对呀,你要是从大到小排序,也是删掉前k条,取到第k条边,但是那样就不对了呀
老哥,您怎么写的啊
因为$k$ 个村庄在最小生成树中只能创建$k-1$条边,所以最多能删去$k-1$条。应该是删掉前$k-1$大的边,输出第$k$大的边。
ororororororz