程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> BZOJ 1821 JSOI 2010 Group 部落劃分 Group Kruskal

BZOJ 1821 JSOI 2010 Group 部落劃分 Group Kruskal

編輯:C++入門知識

BZOJ 1821 JSOI 2010 Group 部落劃分 Group Kruskal


題目大意:給出平面上的一些點,現在要把這些點分成k組,求每組之間的距離的最小值的最大值。

 

思路:很水的題,只需要做一次最小生成樹 ,然後去掉k-1條邊,第k-2條邊就是答案。

 

CODE:
 

#include 
#include 
#include 
#include 
#include 
#include 
#define MAX 1010
using namespace std;
 
struct Point{
    double x,y;
     
    void Read() {
        scanf("%lf%lf",&x,&y);
    }
}point[MAX];
 
inline double Calc(const Point &a,const Point &b)
{
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
 
struct Edge{
    int x,y;
    double len;www.Bkjia.com
     
    Edge(int _,int __,double ___):x(_),y(__),len(___) {}
    Edge() {}
    bool operator <(const Edge &a)const {
        return len < a.len;
    }
}edge[MAX * MAX];
 
int points,edges,k;
int father[MAX];
 
int Find(int x)
{
    if(father[x] == x)  return x;
    return father[x] = Find(father[x]);
}
 
int main()
{
    cin >> points >> k;
    for(int i = 1; i <= points; ++i)
        point[i].Read(),father[i] = i;
    for(int i = 1; i <= points; ++i)
        for(int j = i + 1; j <= points; ++j)
            edge[++edges] = Edge(i,j,Calc(point[i],point[j]));
    sort(edge + 1,edge + edges + 1);
    int added = 0;
    for(int i = 1; i <= edges; ++i) {
        int fx = Find(edge[i].x);
        int fy = Find(edge[i].y);
        if(fx != fy) {
            father[fx] = fy;
            if(++added == points - k + 1) {
                cout << fixed << setprecision(2) << edge[i].len << endl;
                return 0;
            }
        }
    }
    return 0;
}


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved