[C++]白駿4343号:エリアネットワーク

質問リンク

4343号：エリアネットワーク

問題の概要

P個の前進基地を全て繋ぐ.この場合,2つの前進基地は通信のために前進基地との距離が等しい力が必要となる.この場合,必要な力の最大値を求める必要がある.
また、S個の前進基地に衛星通路を設けることができ、衛星通路のある前進基地間では衛星による通信が可能である.

方法

指紋を正しく理解していないため、多くの間違いが発生しています.7ヶ月前に解いて理解できずに諦めて、今日また捕まえました.
MSTにおけるすべての幹線の重みを記憶しながら,クルーズアルゴリズムを用いてMSTを解いた.これらのウェイトは自動的に昇順で格納されます.そして、S番目の重み値の出力を後から開始する.
MSTには、大きな幹線に接続された頂点から衛星が取り付けられる.この場合、残りの幹線の重み付けの最大値は正しい.
S個の頂点に衛星を設置する場合、除外する幹線数はS-1であることを考慮すべきである.

コード#コード#

#include <bits/stdc++.h>

using namespace std;

const int MAX = 501;
int parent[MAX];

struct Edge {
	int v1, v2;
	double weight;

	bool operator<(const Edge& a) { return weight < a.weight; }
};

void init(int sz) { for (int i = 1; i <= sz; i++) parent[i] = i; }

int Find(int a) {
	if (a == parent[a])
		return a;
	return parent[a] = Find(parent[a]);
}

void Union(int a, int b) {
	int pa = Find(a), pb = Find(b);
	parent[pa] = pb;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n;
	cin >> n;

	while (n--) {
		int s, p;
		cin >> s >> p;

		init(p);
	
		vector<pair<int, int>> v(p + 1);
		for (int i = 1; i <= p; i++)
			cin >> v[i].first >> v[i].second;
		 
		vector<Edge> edges;
		for (int i = 1; i <= p; i++)
			for (int j = i + 1; j <= p; j++)
				edges.push_back({ i, j, sqrt(pow(v[i].first - v[j].first, 2) + pow(v[i].second - v[j].second, 2)) });

		sort(edges.begin(), edges.end());
		
		vector<double> res;
		for (auto& i : edges) {
			if (Find(i.v1) != Find(i.v2)) {
				Union(i.v1, i.v2);
				res.push_back(i.weight);
			}
		}

		cout << fixed;
		cout.precision(2);
		cout << res[res.size() - s] << '\n';
	}

	return 0;
}