P1991 无线通讯网 最小生成树

Wild_Of_The_World · 2025-02-09 10:51:02 · 个人记录

这道题的关键在于如何用卫星电话去替换掉最小生成树上的最大边

先是以为两个电话组组成单一的一条边

60pts：

#include<bits/stdc++.h>
using namespace std;
const int N=505;
const int Max=20000;
struct Node{
    int x,y;
}node[N];
double dis[N],ans[N];
int in[N],n,Q;
double Dis(int a,int b){
    return sqrt((node[a].y-node[b].y)*(node[a].y-node[b].y)+
                (node[a].x-node[b].x)*(node[a].x-node[b].x));
}
double Min(double a,double b){return a<b?a:b;}
bool cmp(double a,double b){return a>b;}
int main(){
    cin>>Q>>n;
    for(int i=1;i<=n;i++){
        cin>>node[i].x>>node[i].y;
        dis[i]=Max;
    }
    int m=Max,u,v;
    dis[1]=0;
    for(int i=1;i<=n;i++){
        m=Max;
        for(int j=1;j<=n;j++)
            if(dis[j]<m&&!in[j]) m=dis[j],u=j;
        ans[i]=dis[u];
        in[u]=1;
//      cout<<u<<" "<<dis[u]<<" "<<ans[i]<<endl;
        for(int v=1;v<=n;v++){
            if(u!=v&&!in[v]){
                dis[v]=Min(dis[v],Dis(u,v));
            }   
        } 
    }
    sort(ans+1,ans+1+n,cmp);
    printf("%.2lf",ans[1+Q/2]);
    return 0;
}

每两个电话间可以删去这两个电话与树组成的回路上的一条边

只要把电话设置在最边上就可以删去树上任意一条边

100pts：

#include<bits/stdc++.h>
using namespace std;
const int N=505;
const int Max=20000;
struct Node{
    int x,y;
}node[N];
double dis[N],ans[N];
int in[N],n,Q;
double Dis(int a,int b){
    return sqrt((node[a].y-node[b].y)*(node[a].y-node[b].y)+
                (node[a].x-node[b].x)*(node[a].x-node[b].x));
}
double Min(double a,double b){return a<b?a:b;}
bool cmp(double a,double b){return a>b;}
int main(){
    cin>>Q>>n;
    for(int i=1;i<=n;i++){
        cin>>node[i].x>>node[i].y;
        dis[i]=Max;
    }
    int m=Max,u,v;
    dis[1]=0;
    for(int i=1;i<=n;i++){
        m=Max;
        for(int j=1;j<=n;j++)
            if(dis[j]<m&&!in[j]) m=dis[j],u=j;
        ans[i]=dis[u];
        in[u]=1;
//      cout<<u<<" "<<dis[u]<<" "<<ans[i]<<endl;
        for(int v=1;v<=n;v++){
            if(u!=v&&!in[v]){
                dis[v]=Min(dis[v],Dis(u,v));
            }   
        } 
    }
    sort(ans+1,ans+1+n,cmp);
    printf("%.2lf",ans[Q]);
    return 0;
}

可以用堆优化一下