Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
欢迎参加IJCAI 2020麻将智能体竞赛,大奖等你拿!Welcome to IJCAI 2020 Mahjong AI competition with amazing prizes! | 北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

半小时看题+思路+AC,最有成就感的一题

Posted by csyfZhang at 2020-06-23 16:41:07 on Problem 2349
//二分+生成树
#include<iostream>
#include<cstdio>
#include<string>
#include<string.h>
#include<map>
#include<vector>
#include<algorithm>
#include<queue>
#include<math.h>
using namespace std;
#pragma warning(disable:4996)

#define ll long long
#define vec vector<int>
//#define P pair<int,int>
#define inf 0x3f3f3f3f
#define MAX 505

struct edge {
	int from, to; double d;
	edge(int i, int j, double dis) { from = i, to = j, d = dis; }
};
bool cmp(edge e1, edge e2) { return e1.d < e2.d; }
vector<edge> v;

int x[MAX], y[MAX], T, S, P, kind[MAX];
double dis[MAX][MAX];

//计算距离
double d(int i, int j) {
	return sqrt(1.0*(x[i] - x[j])*(x[i] - x[j]) + (y[i] - y[j])*(y[i] - y[j]));
}

//生成树并查集相关
int find(int k) {
	if (k == kind[k])return k;
	else return kind[k] = find(kind[k]);
}
void unite(int a, int b) { kind[find(b)] = kind[find(a)]; }

//检查最小距离为mid时能否满足要求
bool check(double mid) {
	int cnt = 0, num = 0;
	for (int i = 1; i <= P; i++)kind[i] = i;

	//距离比最短距离小,P个点最多P-1条边
	for (int i = 0; i < v.size() && v[i].d <= mid && cnt < P - 1; i++) {
		edge e = v[i];
		if (find(e.to) != find(e.from)) {
			unite(e.to, e.from);
		}
	}


	for (int i = 1; i <= P; i++) {
		if (find(i) == i)num++;//一个单独的联通子图
	}
	if (num <= S)return true;//子图的个数不多于satellite 的数目-1
	else return false;
}

int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d %d", &S, &P);
		for (int i = 1; i <= P; i++)scanf("%d %d", &x[i], &y[i]);

		v.clear();
		double l = 0, r = -inf;
		for (int i = 1; i <= P; i++)
			for (int j = i + 1; j <= P; j++) {
				dis[i][j] = dis[j][i] = d(i, j);
				if (dis[i][j] >= r)r = dis[i][j] + 1;
				v.push_back(edge(i, j, dis[i][j]));
			}
		sort(v.begin(), v.end(), cmp);

		//二分求最小
		while (r - l >= 0.001) {
			double mid = (r + l) / 2;
			if (check(mid))r = mid;
			else l = mid;
		}

		printf("%.2lf\n", r);
	}
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator