在《程序设计中常用的解题策略》中看到这道题，书上给出了这道题的MST解法，我自己想到的一个做法是“二分+图遍历”。
首先根据点的坐标构造图G；
考虑到d的最优值一定是G中的一条边的权值；
随着d的减小，G中边数减小，因此连通分量可能增加；
考虑到二分策略：O(logm)；
遍历图，计算连通分量的个数N，如果N<=k，此时的d为一个可行解：O(m)；
考虑到浮点误差，在构造边的时候不开根号，而用向量表示。
以下是我的代码（没有测试数据……）：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
const long maxn=507,INF=20007;
typedef struct
{
long u,v,x,y;
}point;
long n,k,tot,ans;
point v[maxn],g[maxn][maxn],edge[maxn*maxn];
bool used[maxn];
int cmp(point a,long dis)
{
return (a.x*a.x+a.y*a.y-dis);
}
void Qsort(long begin,long end)
{
long i=begin,j=end,t=(begin+end)/2;
long mid=edge[t].x*edge[t].x+edge[t].y*edge[t].y;
do{
while(cmp(edge[i],mid)<0) i++;
while(cmp(edge[j],mid)>0) j--;
if(i<=j)
{
point t=edge[i];edge[i]=edge[j];edge[j]=t;
i++;j--;
}
}while(i<=j);
if(begin<j) Qsort(begin,j);
if(i<end) Qsort(i,end);
}
void dfs(long now,long limit)
{
used[now]=true;
for(long i=1;i<=n;i++)
if(!used[i]&&cmp(g[now][i],limit)<=0)
{
used[i]=true;
dfs(i,limit);
}
}
long travel(point p)
{
long dis=p.x*p.x+p.y*p.y,re;
re=0;
memset(used,false,sizeof(used));
for(long i=1;i<=n;i++)
if(!used[i])
{
dfs(i,dis);
re++;
}
return re;
}
long bsearch(long begin,long end)
{
long re=end;
while(begin<end)
{
long mid=(begin+end)/2;
if(travel(edge[mid])<=k)
{
re=mid;
end=mid;
}
else begin=mid+1;
}
return re;
}
int main()
{
//*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
//*/
scanf("%ld%ld",&n,&k);
for(long i=1;i<=n;i++)
scanf("%ld%ld",&v[i].x,&v[i].y);
// Input
for(long i=1;i<=n;i++)
for(long j=1;j<=n;j++)
g[i][j].x=g[i][j].y=INF;
tot=1;
edge[tot].u=edge[tot].v=edge[tot].x=edge[tot].y=0;
for(long i=1;i<=n;i++)
for(long j=1;j<=n;j++)
if(i!=j)
{
g[i][j].u=i;
g[i][j].v=j;
g[i][j].x=abs(v[i].x-v[j].x);
g[i][j].y=abs(v[i].y-v[j].y);
tot++;
edge[tot]=g[i][j];
}
// Distance
Qsort(1,tot);
//for(long i=1;i<=tot;i++)printf("%ld %ld %ld %ld\n",edge[i].u,edge[i].v,edge[i].x,edge[i].y);
ans=bsearch(1,tot);
printf("%.2lf\n",sqrt(edge[ans].x*edge[ans].x+edge[ans].y*edge[ans].y));
return 0;
}
posted on 2010-02-20 14:14
lee1r 阅读(274)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：图论