BZOJ 1821 JSOI2010 部落劃分 Group Kruskal
題目大意：給定平面上的n個點，要求將這n個點劃分為k個集合，使劃分後任意兩個集合中最近兩點的距離的最大值最小，輸出這個最小值
考慮這n個點之間所有的連邊 我們要讓長邊保留 就盡量選取短邊鏈接
於是就是求加入n-k條邊的最小生成森林 由於輸出下一個最小值 因此Kruskal加入第n-k+1條邊時輸出邊權即可
#include
#include
#include
#include
#include
#include
#define M 1100
using namespace std;
struct point{
int x,y;
void Read()
{
scanf("%d%d",&x,&y);
}
}points[M];
struct edge{
int x,y;
double dis;
edge() {}
edge(int _,int __,double ___):
x(_),y(__),dis(___) {}
bool operator < (const edge &e) const
{
return dis < e.dis;
}
}edges[1001001];
int n,m,k;
double Distance(const point &p1,const point &p2)
{
return sqrt( (p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y) );
}
namespace Union_Find_Set{
int fa[M];
inline void Union(int x,int y)
{
fa[x]=y;
}
int Find(int x)
{
if(!fa[x]||fa[x]==x)
return fa[x]=x;
return fa[x]=Find(fa[x]);
}
}
double Kruskal(int temp)
{
using namespace Union_Find_Set;
int i;
sort(edges+1,edges+m+1);
for(i=1;i<=m;i++)
{
int x=Find(edges[i].x);
int y=Find(edges[i].y);
if(x==y) continue;
Union(x,y);
if(!--temp)
return edges[i].dis;
}
return 0;
}
int main()
{
int i,j;
cin>>n>>k;
for(i=1;i<=n;i++)
points[i].Read();
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i!=j)
edges[++m]=edge(i,j,Distance(points[i],points[j]) );
cout<
