「模拟8.17」star way to heaven(并查集，最小生成树)

80分打法

首先二分最后答案，答案即为r，可看作以每个k为圆心r为半径的圆

我们进行并查集维护，维护相交的圆的边界

最后判断是否存在圆将上下边界覆盖，如有证明不行

 1 #include<iostream>

 2 #include<cstdio>

 3 #include<cstring>

 4 #include<cmath>

 5 #include<algorithm>

 6 #include<string>

 7 #include<vector>

 8 #include<map>

 9 #include<set>

10 #define min(a,b) a>b?b:a

11 #define max(a,b) a>b?a:b

12 #define int long long

13 #define MAXN 1000001

14 using namespace std;

15 int fa[MAXN];

16 double l_y[MAXN],r_y[MAXN];

17 int x[MAXN],y[MAXN];

18 int find(int x)

19 {

20      if(fa[x]==x)return fa[x];

21      return fa[x]=find(fa[x]);

22 }

23 bool judge(int xx,int yy,double r)

24 {

25      double deta_x=abs(x[xx]-x[yy]);

26      double deta_y=abs(y[xx]-y[yy]);

27      //printf("deta_x=%lld deta_y=%lld\n",deta_x,deta_y);

28      if((double)deta_x*deta_x+(double)deta_y*deta_y<(2.0*r)*(r*2.0))return 1;

29      return 0;

30 }

31 int n,m,k;

32 bool work(double cir)

33 {

34      for(int i=1;i<=k;++i)fa[i]=i;

35      for(int i=1;i<=k;++i)

36      {

37          l_y[i]=(double)y[i]-cir;r_y[i]=(double)y[i]+cir;

38      }

39      for(int i=1;i<=k;++i)

40      {

41          for(int j=1;j<=k;++j)

42          {

43              //printf("i=%lld j=%lld\n",i,j);

44              int xx=find(i);int yy=find(j);

45              if(xx==yy)continue;

46              if(judge(i,j,cir))

47              {

48                 fa[yy]=xx;

49                 l_y[yy]=l_y[xx]=min(l_y[yy],l_y[xx]);

50                 r_y[yy]=r_y[xx]=max(r_y[yy],r_y[xx]);

51                 //printf("l_y[%lld]=%.4lf r_y[%lld]=%.4lf\n",xx,l_y[xx],xx,r_y[xx]);

52              }

53          }

54      }

55      for(int i=1;i<=k;++i)

56      {

57          if(l_y[find(i)]<cir&&r_y[find(i)]>m-cir)

58          {

59              //printf("l_y[%lld]=%.4lf r_y[%lld]=%.4lf\n",find(i),l_y[find(i)],find(i),r_y[find(i)]);

60              return 0;

61          }

62      }

63      return 1;

64 }

65 void second_divided()

66 {

67      double l=0.0,r=m;

68      while(l+0.0000001<r)

69      {

70            double mid=(l+r)/2;

71            //printf("mid=%.4lf\n",mid);

72            if(work(mid))

73            {

74               l=mid;

75            }

76            else r=mid;

77      }

78      if(work(r))printf("%.6lf\n",r);

79      else printf("%.6lf\n",l);

80 }

81 signed main()

82 {

83      scanf("%lld%lld%lld",&n,&m,&k);

84      for(int i=1;i<=k;++i)scanf("%lld%lld",&x[i],&y[i]);

85      second_divided();

86 }

100分

开始是很难看出这是最小生成树，（听说是什么欧几里得最小生成树，非常神奇）

对于最小生成树有几个性质：（自己瞎写的，可能不对）

1.最小生成树包含两点之间路径的最小边

2.最小生成树生成的边和最小

对于此题，我们尽量选边权小的边，构成最小生成树，

选出从上边界到下边界的最大边权，除二既是答案

最小生成树保证了选出这个边后，其他圆只会离他更远，所以正确

另外学习了prim算法

 1 #include<iostream>

 2 #include<cstdio>

 3 #include<cstring>

 4 #include<cmath>

 5 #include<algorithm>

 6 #include<string>

 7 #include<vector>

 8 #include<map>

 9 #include<set>

10 #define min(a,b) a>b?b:a

11 #define max(a,b) a>b?a:b

12 #define int long long

13 #define MAXN 1000001

14 using namespace std;

15 double disx[MAXN],disy[MAXN];

16 int n,m,k;

17 double d[MAXN];int vis[MAXN];int fa[MAXN];

18 double poww(double x)

19 {

20     return x*x;

21 }

22 struct no{int to,n;double w;}e[MAXN*2];int head[MAXN],tot;

23 void add(int u,int v,double w)

24 {

25      e[++tot].to=v;e[tot].n=head[u];e[tot].w=w;head[u]=tot;

26 }

27 double cal(int x,int y)

28 {

29     if(x>y)swap(x,y);

30     if(x==k+1&&y==k+2)return (double)m;

31     if(y==k+1)return disy[x];

32     if(y==k+2)return (double)m-disy[x];

33     //printf("cal%.4lf\n",sqrt(poww(disx[x]-disx[y])+poww(disy[x]-disy[y])));

34     return sqrt(poww(disx[x]-disx[y])+poww(disy[x]-disy[y]));

35 }

36 void prim()

37 {

38      memset(vis,0,sizeof(vis));

39      for(int i=1;i<=k+2;++i)d[i]=100000000000.0;

40      d[1]=0;

41      for(int i=1;i<k+2;++i)

42      {

43          double minn=100000000000.0;int x=0;

44          for(int j=1;j<=k+2;++j)

45          {

46              if(!vis[j]&&d[j]<minn)

47              {

48                   minn=d[j];x=j;

49              }

50          }

51          vis[x]=1;

52          for(int j=1;j<=k+2;++j)

53          {

54              if(!vis[j])

55              {

56                 double dis=cal(x,j);

57                 if(dis<d[j])

58                 {

59                     d[j]=dis;

60                     fa[j]=x;

61                     //printf("j=%lld x=%lld dis=%.4lf\n",j,x,d[j]);

62                 }

63              }

64          }

65      }

66      for(int i=2;i<=k+2;++i)

67      {

68          add(i,fa[i],d[i]);add(fa[i],i,d[i]);

69          //printf("%lld %lld %.4lf\n",fa[i],i,d[i]);

70      }

71 }

72 double ans=0.0;

73 void DFS(int x,double w,int fa)

74 {

75      if(x==k+2){ans=w;return ;}

76      for(int i=head[x];i;i=e[i].n)

77      {

78          int to=e[i].to;

79          if(to==fa)continue;

80          DFS(to,max(w,e[i].w),x);

81      }

82 }

83 signed main()

84 {

85     scanf("%lld%lld%lld",&n,&m,&k);

86     for(int i=1;i<=k;++i)

87     {

88         scanf("%lf%lf",&disx[i],&disy[i]);

89     }

90     prim();

91     DFS(k+1,0,0);

92     printf("%.7lf\n",ans/2);

93 }

巴特西

「模拟8.17」star way to heaven(并查集，最小生成树)

最新文章

热门文章