arctic network(最小生成树).cpp

杭电acm解题报告2001---2099.

//标程使用二分枚举，分析见WC2004 吴景岳论文
#include <cstdio>
#include <string>
#include <vector>
#include <cmath>
#include <functional>
#include <algorithm>
using namespace std;

const int MAX = 510;
int p,s,n;
int vi[MAX][2];
double dist[MAX][MAX];
vector<double> mst;

void prime() {
	int i,j;
	double len[MAX];
	mst.clear();
	for(i=1;i<p;i++) len[i] = dist[0][i];
	len[0] = -1;
	for(i=1;i<p;i++) {
		int minp = -1;
		double minv = INT_MAX;
		for(j=0;j<p;j++) {
			if(len[j] > 0 && len[j] < minv) {
				minv = len[j];
				minp = j;
			}
		}
		len[minp] = -1;
		mst.push_back(minv);
		for(j=0;j<p;j++) {
			if(len[j] > 0) len[j] = min(len[j], dist[minp][j]);
		}
	}
}

int main() {
	scanf("%d", &n);
	while(n --) {
		scanf("%d %d", &s,&p);
		int i, j;
		for(i=0;i<p;i++) scanf("%d %d", &vi[i][0], &vi[i][1]);
		for(i=0;i<p;i++) {
			dist[i][i] = 0;
			for(j=i+1;j<p;j++) {
				dist[i][j] = dist[j][i] = sqrt(1.0*(vi[i][0]-vi[j][0])*(vi[i][0]-vi[j][0]) + (vi[i][1]-vi[j][1])*(vi[i][1]-vi[j][1]));
			}
		}
		prime();
		sort(mst.begin(), mst.end(), greater<double>());
		if(s <= 1) printf("%.2lf\n", mst[0]);
		else if(s >= p) puts("0");
		else printf("%.2lf\n", mst[s-1]);
	}
}