BZOJ1821 [JSOI2010]部落划分 Group

2014.12.19 12:39 Fri| 0 visits oi_2015| 2015_刷题日常| Text

Solution

这或许是JSOI2010中最水的一道题吧……

题目中要求把野人们分成K个部落,那么可以将每两个野人居住的地点间连结一条边权为其间距离的边。对这些边按照边权从小到大排序,贪心加入并查集中维护,过程类似于Kruskal算法。

Code

#include <bits/stdc++.h>
using namespace std;
#define inf 1000000000
#define sqr(x) ((x)*(x))
#define N 1005

struct point
{
    double x,y;
    point(double _x=0.0,double _y=0.0):x(_x),y(_y) {}
    friend double dist(const point &a,const point &b)
    {
        return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));
    }
    void read()
    {
        cin>>x>>y;
    }
};

struct edge
{
    int x,y; double w;
    edge(int _x=0,int _y=0,double _w=0.0):x(_x),y(_y),w(_w) {}
    bool operator <(const edge &x) const
    {
        return w<x.w;
    }
};

point p[N];
edge e[N*N];
int n,m,k,fa[N];

int find(int x)
{
    if(x==fa[x]) return x;
    return fa[x]=find(fa[x]);
}

double kruskal()
{
    int re=0;
    sort(e+1,e+m+1);
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int t=0,i=1;i<=m;i++)
    {
        int fx=find(e[i].x),fy=find(e[i].y);
        if(fx!=fy)
        {
            fa[fx]=fy, re+=e[i].w;
            if(++t==n-k+1) return e[i].w;
        }
    }
    return 0.0;
}

int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        p[i].read();
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            e[++m]=edge(i,j,dist(p[i],p[j]));
    cout<<fixed<<setprecision(2)<<kruskal()<<endl;
}