P1991 无线通讯网最小生成树

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

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

60pts：

CPP

#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：

CPP

#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;
}

可以用堆优化一下

P1991 无线通讯网最小生成树

文章操作

相关推荐

评论

P1991 无线通讯网最小生成树