【c++ 图论例题学习】洛谷 p1991 无线通讯网 - 思路详解

2 40 1000 3000 600150 750

212.13

#include<cmath>#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;struct edge{	long long u,v;	double w;	bool operator<(const edge &a)const{		return w<a.w;//以结构体中的w作为排序比较大小的对象	}}e[10101000];int ax[10010101],ay[10010101];//记录数据用int st(int x,int y){	return 1ll*(ax[x]-ax[y])*(ax[x]-ax[y])+1ll*(ay[x]-ay[y])*(ay[x]-ay[y]);//这里记得要加ill*，因为本题的数据范围比较大，如果不加1ll*将计算结果改成lang lang 类型就会影响计算结果。}//计算结果先不开方，下文会统一处理int ecnt=0;void add(int u,int v,int w){	e[++ecnt].u=u;	e[ecnt].w=w;	e[ecnt].v=v;}int f[101010];long long n,m;int getf(int x){	return x==f[x]?x:f[x]=getf(f[x]);}int main(){	cin>>n>>m;	for(int i=1;i<=m;i++){		cin>>ax[i]>>ay[i];	}	for(int i=1;i<m;i++){		for(int j=i+1;j<=m;j++){			add(i,j,st(i,j));//循环避免重复同一个点		}	}	for(int i=1;i<=m;i++){		f[i]=i;	}	sort(e+1,e+1+ecnt);	int cnt=0;	double ans=-1;	for(int i=1;i<=ecnt;i++){		int u=getf(e[i].u);		int v=getf(e[i].v);		if(u!=v){//如果没有连通就加边并且记录数据			cnt++;			ans=max(ans,sqrt(e[i].w));//在这里开方处理，注意ans的数据类型			f[u]=v;		}		if(cnt==m-n){//这里的m就是pp，n就是ss，由题意，ss个基站不需要加边，所以m-n代表全部连通的边数			break;		}	}printf("%.2lf",ans);//注意输出格式}