宇宙神との交感1774号

質問する

黄仙子は宇宙神と交流できる魂です.しかし、宇宙神は一つだけではないので、黄仙子は毎回多くの宇宙神と交流しなければならない.このような状況で、新しい宇宙神は黄仙子を利用した.
しかし、偉大な宇宙神たちは黄仙子と直接結びつく必要はない.黄仙子や宇宙神と交流できる宇宙神がいるので、新しい宇宙神はそれらの宇宙神を通じて黄仙子と交流することができます.
宇宙神との交流は、宇宙神と皇太子や宇宙神の間の精神通路を通じて行われる.しかし、宇宙神との交流は難しいので、黄仙子はこれらの通路が長いのが好きではありません.通路が長ければ長いほど、大変なので.
また、私たちは3次元座標系で表すことができる世界に住んでいますが、宇宙神と黄仙子は2次元座標系で表すことができる世界に住んでいます.チャネルの長さは2 D座標系の距離に等しい.
すでに皇太子氏につながる、あるいは宇宙神につながる通路が存在する.私たちは黄善子さんを助けて、まだつながっていない宇宙神をつなぎます.再創造が必要な精神通路の長さの総和を最小にし、通路を作り出し、「パンベッド」を叫ぶのを助ける.

まず、すべての宇宙神の部分をつなぐことで、ユニオン-Findアルゴリズムを思いついた.また,それぞれ宇宙神間の距離を求めた後,これを基準に並べ替え,より小さな距離を持つ2つの宇宙神が既存の集合に含まれているかどうかを計算し,解く方向に近づく.

struct LengthInfo {
	int n1;
	int n2;
	double length;

	LengthInfo(int a, int b, double l) {
		n1 = a;
		n2 = b;
		length = l;
	}
};

struct Pos {
	double x;
	double y;

	Pos() {

	}

	Pos(double xVal, double yVal) {
		x = xVal;
		y = yVal;
	}
};

まず2つの構造体を作製した.
LengthInfo:2つの宇宙神とその宇宙神との距離を表します.
Pos:x座標、y座標

priority_queue<LengthInfo, vector<LengthInfo>, Sort> pq;
int parent[1001];
Pos pos[1001];

次に、2つのポイント間で昇順にソートされた優先順位キュー、本人の親番号を含むparent配列、x座標とy座標を含むpos配列を作成します.

	int n;
	int m;
	cin >> n;
	cin >> m;

	for (int i = 1; i <= n; i++) {
		parent[i] = i;
	}

	for (int i = 0; i < n; i++) {
		int a;
		int b;
		cin >> a;
		cin >> b;

		pos[i + 1] = Pos(a, b);

		for (int j = 1; j <= i; j++) {
			double length = sqrt(pow(a - pos[j].x, 2) + pow(b - pos[j].y, 2));
			pq.push(LengthInfo(j, i + 1, length));
		}
	}

入力と初期化が完了したら

for (int i = 0; i < m; i++) {
		int a;
		int b;
		cin >> a;
		cin >> b;

		Union(a, b);
	}

問題の部分に従って合併した.

int Find(int n) {

	if (parent[n] == n) {
		return n;
	}

	return Find(parent[n]);
}

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

UnionとFind関数も定義されています...

	double sum = 0;
	while (!pq.empty()) {
		LengthInfo li = pq.top();
		pq.pop();

		int n1 = li.n1;
		int n2 = li.n2;

		if (Find(n1) != Find(n2)) {
			Union(n1, n2);
			sum += li.length;
		}
	}

本当に問題を解くコードはこれらです.優先順位キューでは距離順に昇順に並べられているので、距離は小さい順に抽出され、距離を構成する2つの番号のルート値が同じ値でない場合(両方の番号が1つの図形に接続されていない場合)、1つの図形に統合され、総距離が計算されます.

#include <iostream>
#include <queue>
#include <cmath>

using namespace std;

struct LengthInfo {
	int n1;
	int n2;
	double length;

	LengthInfo(int a, int b, double l) {
		n1 = a;
		n2 = b;
		length = l;
	}
};

struct Sort {
	bool operator()(LengthInfo l1, LengthInfo l2) {
		return l1.length > l2.length;
	}
};


struct Pos {
	double x;
	double y;

	Pos() {

	}

	Pos(double xVal, double yVal) {
		x = xVal;
		y = yVal;
	}
};

priority_queue<LengthInfo, vector<LengthInfo>, Sort> pq;
int parent[1001];
Pos pos[1001];

int Find(int n) {

	if (parent[n] == n) {
		return n;
	}

	return Find(parent[n]);
}

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

int main() {

	int n;
	int m;
	cin >> n;
	cin >> m;

	for (int i = 1; i <= n; i++) {
		parent[i] = i;
	}

	for (int i = 0; i < n; i++) {
		int a;
		int b;
		cin >> a;
		cin >> b;

		pos[i + 1] = Pos(a, b);

		for (int j = 1; j <= i; j++) {
			double length = sqrt(pow(a - pos[j].x, 2) + pow(b - pos[j].y, 2));
			pq.push(LengthInfo(j, i + 1, length));
		}
	}

	for (int i = 0; i < m; i++) {
		int a;
		int b;
		cin >> a;
		cin >> b;

		Union(a, b);
	}

	double sum = 0;
	while (!pq.empty()) {
		LengthInfo li = pq.top();
		pq.pop();

		int n1 = li.n1;
		int n2 = li.n2;

		if (Find(n1) != Find(n2)) {
			Union(n1, n2);
			sum += li.length;
		}
	}

	cout << fixed;
	cout.precision(2);
	cout.setf(ios::showpoint);
	cout << sum << endl;
	return 0;
}

コード全体がそうです.