网站建设设计书,东莞网站优化排名网站,一个域名可以做两个网站吗,自己做网站赚钱案例正题 题目大意
有n个点#xff0c;给出坐标#xff0c;选择所有距离在k之内的边要求联通所有点#xff0c;求最小的k。 解题思路
垃圾解法
用二分答案然后加并查集求是否联通。 时间复杂度#xff1a;O(mlogn)O(mlogn)正解
按距离排序#xff0c;然后连边到所有岛都联…正题 题目大意
有n个点给出坐标选择所有距离在k之内的边要求联通所有点求最小的k。 解题思路
垃圾解法
用二分答案然后加并查集求是否联通。 时间复杂度O(mlogn)O(mlogn)O(mlogn)
正解
按距离排序然后连边到所有岛都联通为止。 时间复杂度O(mlogm)O(mlogm)O(mlogm) 垃圾解法的代码
#includecstdio
#includealgorithm
#includecmath
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.wyxx.w;}
int find(int x)//并查集
{return father[x]x?x:father[x]find(father[x]);}
void unionn(int x,int y)//并查集
{int fafind(x),fbfind(y);if (fafb) return;else{if (fafb) father[fb]fa;else father[fa]fb;s--;}
}
bool check(double ll){//判断可否联通for (int i1;in;i)father[i]i;sn;for (int i1;itot;i)if(lla[i].w) return false;else{unionn(a[i].from,a[i].to);if (s1) return true;}return false;
}
int main()
{scanf(%d,n);for (int i1;in;i)scanf(%d%d%d,dx[i],dy[i],dr[i]);for (int i1;in;i)for (int ji1;jn;j){a[tot].fromi;a[tot].toj;double lwdis(dx[i],dy[i],dx[j],dy[j])-dr[i]-dr[j];a[tot].wlw;if (a[tot].w0) a[tot].w0;//输入}sort(a1,a1tot,cmp);int l1,r2000,mid;while (lr)//二分{mid(lr)/2;if (check((double)mid)) rmid-1;else lmid1;}printf(%d,l);
} 对拍
数据生成
#includecstdio
#includecstdlib
#includectime
#define random(x) rand()*rand()%x1
using namespace std;
int n,m;
int main()
{freopen(air.in,w,stdout);srand((unsigned)time(0));nrandom(1000);//n1000;printf(%d\n,n);for (int i1;in;i){printf(%d %d %d\n,random(1000),random(1000),random(5));}
}
判断加对拍
#includecstdio
#includecstdlib
#includectime
#includecmath
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 fafind(x),fbfind(y);if (fafb) return;else{if (fafb) father[fb]fa;else father[fa]fb;s--;}
}
int main()
{for (int ti1;ti10000;ti){system(airdata.exe);double stclock();system(air.exe);double edclock();if (ed-st1000){printf(TLE);break;}freopen(air.in,r,stdin);scanf(%d,n);for (int i1;in;i)scanf(%d%d%d,dx[i],dy[i],dr[i]);fclose(stdin);freopen(air.out,r,stdin);scanf(%d,l);sn;okfalse;for (int i1;in;i)father[i]i;for (int i1;in;i){for (int j1;jn;j){double lwdis(dx[i],dy[i],dx[j],dy[j])-dr[i]-dr[j];if (lwl){unionn(i,j);}if (s1) oktrue;}if (s1) oktrue;}if (s!1){printf(WA);break;}fclose(stdin);printf(AC point:%d time:0.%0.lf\n,ti,ed-st);}
}