在《程序設計中常用的解題策略》中看到這道題，書上給出了這道題的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 閱讀(283)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：圖論