正題

---

題目大意

有n個點，給出坐標，選擇所有距離在k之內的邊要求聯通所有點，求最小的k。

---

解題思路

垃圾解法

用二分答案然后加并查集求是否聯通。
時間復雜度：O(mlogn)O(mlogn)

正解

按距離排序，然后連邊到所有島都聯通為止。
時間復雜度：O(mlogm)O(mlogm)

---

垃圾解法的代碼

#include<cstdio> #include<algorithm> #include<cmath> using namespace std; struct node{int from,to;double w; }a[1000001]; int n,dx[1001],dy[1001],dr[1001],father[1001],s,tot; double dis(double x1,double y1,double x2,double y2) {return sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1)); }//求距離 bool cmp(node xxx,node yxx)//排序 {return xxx.w<yxx.w;} int find(int x)//并查集 {return father[x]==x?x:father[x]=find(father[x]);} void unionn(int x,int y)//并查集 {int fa=find(x),fb=find(y);if (fa==fb) return;else{if (fa<fb) father[fb]=fa;else father[fa]=fb;s--;} } bool check(double ll){//判斷可否聯通for (int i=1;i<=n;i++)father[i]=i;s=n;for (int i=1;i<=tot;i++)if(ll<a[i].w) return false;else{unionn(a[i].from,a[i].to);if (s==1) return true;}return false; } int main() {scanf("%d",&n);for (int i=1;i<=n;i++)scanf("%d%d%d",&dx[i],&dy[i],&dr[i]);for (int i=1;i<n;i++)for (int j=i+1;j<=n;j++){a[++tot].from=i;a[tot].to=j;double lw=dis(dx[i],dy[i],dx[j],dy[j])-dr[i]-dr[j];a[tot].w=lw;if (a[tot].w<0) a[tot].w=0;//輸入}sort(a+1,a+1+tot,cmp);int l=1,r=2000,mid;while (l<=r)//二分{mid=(l+r)/2;if (check((double)mid)) r=mid-1;else l=mid+1;}printf("%d",l); }

---

對拍

數據生成

#include<cstdio> #include<cstdlib> #include<ctime> #define random(x) rand()*rand()%x+1 using namespace std; int n,m; int main() {freopen("air.in","w",stdout);srand((unsigned)time(0));n=random(1000);//n=1000;printf("%d\n",n);for (int i=1;i<=n;i++){printf("%d %d %d\n",random(1000),random(1000),random(5));} }

判斷加對拍

#include<cstdio> #include<cstdlib> #include<ctime> #include<cmath> using namespace std; int n,dx[1001],dy[1001],dr[1001],father[1001],s,l; bool ok; double dis(double x1,double y1,double x2,double y2) {return sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1)); } int find(int x) {return father[x]==x?x:father[x]=find(father[x]);} void unionn(int x,int y) {int fa=find(x),fb=find(y);if (fa==fb) return;else{if (fa<fb) father[fb]=fa;else father[fa]=fb;s--;} } int main() {for (int ti=1;ti<=10000;ti++){system("airdata.exe");double st=clock();system("air.exe");double ed=clock();if (ed-st>1000){printf("TLE");break;}freopen("air.in","r",stdin);scanf("%d",&n);for (int i=1;i<=n;i++)scanf("%d%d%d",&dx[i],&dy[i],&dr[i]);fclose(stdin);freopen("air.out","r",stdin);scanf("%d",&l);s=n;ok=false;for (int i=1;i<=n;i++)father[i]=i;for (int i=1;i<=n;i++){for (int j=1;j<=n;j++){double lw=dis(dx[i],dy[i],dx[j],dy[j])-dr[i]-dr[j];if (lw<=l){unionn(i,j);}if (s==1) ok=true;}if (s==1) ok=true;}if (s!=1){printf("WA");break;}fclose(stdin);printf("AC point:%d time:0.%0.lf\n",ti,ed-st);} }

總結

以上是生活随笔為你收集整理的【2018.5.19】模拟赛之四-ssl2435 航空公司【并查集,二分】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。