题解 P1783 【海滩防御】

· · 题解

这题刚开始很多人会想到二分，二分答案，然后看看是否能绕过所有信号塔，但是，这样写明显超时，对于任何一个点，要找到离它最近的信号塔需要O(n)的时间，再乘上M*L（L=海滩的长度）不超时才怪呢。

这一题的本质就是封锁海滩，即用信号塔的工作范围将两边的边界连在一起。所以，这题就是求一条从第0列到第n列的最短路径，用点与边界的距离作为权值，点与点之间的距离的二分之一作为权值，构图完成后，用Dijkstra算法求最短路就可以了。当然用Kruskal算法并查集结构依次加最小边，直到两条边界被连在一起也是可以的。但是要注意最短路的长度是路径上边权的最大值，而不是边权之和。


#include<stdio.h> //By C_SUNSHINE
#include<math.h>
#include<iostream>
using namespace std;
const int maxn=805;
int n,w;
struct edge
{
       int u,v;
       float c;
}e[maxn*maxn];
int x[maxn],y[maxn],W;
int f[maxn];
float getdist(int i,int j)
{
  return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}
bool cmp(edge e1,edge e2)
{
  return e1.c<e2.c;
}
int getfather(int root)
{
  if(f[root]==-1)return root;
  else return f[root]=getfather(f[root]);
}
void init()
{
     memset(f,-1,sizeof(f));
     n=0;w=0;
     scanf("%d%d",&W,&n);
     if(n==0)exit(0);
     int i,j;
     for(i=1;i<=n;i++)
       scanf("%d%d",y+i,x+i);
     for(i=1;i<n;i++)
       for(j=i+1;j<=n;j++)
         e[++w]=(edge){i,j,getdist(i,j)/2};
     for(i=1;i<=n;i++)
     {
         e[++w]=(edge){i,0,y[i]};
         e[++w]=(edge){i,n+1,W-y[i]};
     }
     sort(e+1,e+w+1,cmp);
}
void work()
{
     int i=0,p,q;
     while(getfather(0)!=getfather(n+1))
     {
       i++;
       p=getfather(e[i].u);
       q=getfather(e[i].v);
       if(p!=q)f[p]=q;
     }
     printf("%.2f\n",e[i].c);
}
int main()
{
    init();
    work();
    return 0;
}