AcWing 1145. 北极通讯网络（二分）

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 1145. 北极通讯网络（二分）原题链接中等

作者：

Tenshi , 2021-03-16 23:09:36 , 所有人可见 , 阅读 674

分析

二分做法~~粗暴无脑~~，挺好的。
大体思路是：

预处理出边权
二分出一个连边的上界，对边权进行排序
对于二分的check，如果联通块的数量 $\leqslant k$ 那么满足check() ，否则不满足。

感谢 @斗牛犬指出问题 orz

#include<bits/stdc++.h>
using namespace std;

const int N=505;
const double eps=1e-6;

int n,k;
int f[N];

struct Ver{
    double x,y;
}v[N];

struct Edge{
    int u,v;
    double w;
    bool operator<(const Edge &o)const{
        return w<o.w;
    }
}e[N*N*2];

double cal(int a,int b){
    return sqrt((v[a].x-v[b].x)*(v[a].x-v[b].x)+(v[a].y-v[b].y)*(v[a].y-v[b].y));
}

int tot;
void get_edges(){
    for(int i=1;i<=n-1;i++)
        for(int j=i+1;j<=n;j++){
            e[++tot]={i,j,cal(i,j)};
        }
}

int find(int x){return x==f[x]?x:f[x]=find(f[x]);}

bool check(double d){
    for(int i=1;i<=n;i++) f[i]=i;

    int idx=tot;
    for(int i=1;i<=tot;i++){
        double w=e[i].w;
        if(w>d+eps){
            idx=i-1;
            break;
        }
    }

    int res=0;
    for(int i=1;i<=idx;i++){
        int u=e[i].u, v=e[i].v;
        int pu=find(u), pv=find(v);
        if(pu!=pv){
            res++;
            f[pu]=pv;
        }
    }

    return n-res<=k;
}

int main(){
    cin>>n>>k;
    if(!k) k=1;
    for(int i=1;i<=n;i++){
        double x,y; cin>>x>>y;
        v[i]={x,y};
    }

    get_edges();

    sort(e+1,e+1+tot);

    double l=0,r=e[tot].w;
    while(l+eps<r){
        double mid=(l+r)/2;
        if(check(mid)) r=mid;
        else l=mid;
    }
    printf("%.2lf",l);

    return 0;
}

9 评论

斗牛犬 10个月前

楼主的代码加个特判，不然会wa，原因应该是k==0的时候，连通块个数应该为1个

#include<bits/stdc++.h>
using namespace std;

const int N=505;
const double eps=1e-6;

int n,k;
int f[N];

struct Ver{
    double x,y;
}v[N];

struct Edge{
    int u,v;
    double w;
    bool operator<(const Edge &o)const{
        return w<o.w;
    }
}e[N*N*2];

double cal(int a,int b){
    return sqrt((v[a].x-v[b].x)*(v[a].x-v[b].x)+(v[a].y-v[b].y)*(v[a].y-v[b].y));
}

int tot;
void get_edges(){
    for(int i=1;i<=n-1;i++)
        for(int j=i+1;j<=n;j++){
            e[++tot]={i,j,cal(i,j)};
        }
}

int find(int x){return x==f[x]?x:f[x]=find(f[x]);}

bool check(double d){
    for(int i=1;i<=n;i++) f[i]=i;

    int idx=tot;
    for(int i=1;i<=tot;i++){
        double w=e[i].w;
        if(w>d+eps){
            idx=i-1;
            break;
        }
    }

    int res=0;
    for(int i=1;i<=idx;i++){
        int u=e[i].u, v=e[i].v;
        int pu=find(u), pv=find(v);
        if(pu!=pv){
            res++;
            f[pu]=pv;
        }
    }

    return n-res<=k;
}

int main(){
    cin>>n>>k;
    if(k == 0)k = 1;
    for(int i=1;i<=n;i++){
        double x,y; cin>>x>>y;
        v[i]={x,y};
    }

    get_edges();

    sort(e+1,e+1+tot);

    double l=0,r=e[tot].w;
    while(l+eps<r){
        double mid=(l+r)/2;
        if(check(mid)) r=mid;
        else l=mid;
    }
    printf("%.2lf",l);

    return 0;
}