์๊ณ ๋ฆฌ์ฆ
- ํฌ๋ฃจ์ค์นผ
- ๋ชจ๋ ํ๋ ์ฌ์ด์ ๊ฑฐ๋ฆฌ๋ฅผ ๊ณ์ฐํ๊ณ , ์ ์ชฝ ํ๋์ ๋ฒํธ์ ๊ฑฐ๋ฆฌ๋ฅผ ๋ฒกํฐ์ ์ ์ฅํ๋ค.
- ๊ฑฐ๋ฆฌ์์ผ๋ก ์ ๋ ฌํ๊ณ , ํฌ๋ฃจ์ค์นผ ์๊ณ ๋ฆฌ์ฆ ์ํ
- ์ด๋, ๋จ์ํ union-find ์๊ณ ๋ฆฌ์ฆ์ผ๋ก ํ๋ฉด find์์ ์๊ฐ์ด๊ณผ๊ฐ ๋๋ค.
- ๋ฐ๋ผ์ set์ ํ์ฉํด์ ํฌ๋ฃจ์ค์นผ์ ํ๋ฉด ๋๋ค.
ํค๋งจ ์ง์
- set์ ์ด์ฉํด์ ํ ๋, ์๋ก ๋ค๋ฅธ ์งํฉ์ด์๋ค๊ฐ ํฉ์ณ์ง๋, ํ๋๋ง ์ฎ๊ธฐ๋ฉด ์๋๋ค. ๊ทธ set์ ์ํด์๋ ๋ชจ๋ ์ ์ ๋ค ์ฎ๊ฒจ์ผํจ
- ๊ผญ ์ฒซ๋ฒ์งธ ์งํฉ์ผ๋ก ํฉ์ณ์ง์ง ์๋๋ค. ๋ฐ๋ผ์, ๋ชจ๋ ์ ๋ค์ด ๊ฐ์ ์งํฉ์ ์๋์ง ํ๋ํ๋ ํ์ธํด๋ด์ผํ๋ค.
์ฝ๋
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <set>
using namespace std;
struct node {
int first;
int second;
int length;
bool operator< (node a) {
return length < a.length;
}
};
vector<pair<int, int>> field;
vector<node> lengths;
vector<set<int>> unionset;
int N, C, parent[2000];
long long result;
void calcLengths();
bool kruskal();
int power(int a) {
return a * a;
}
int main() {
cin >> N >> C;
int a, b;
while (N--) {
cin >> a >> b;
field.push_back({ a, b });
}
N = field.size();
calcLengths();
memset(parent, -1, sizeof(parent));
sort(lengths.begin(), lengths.end());
if (kruskal())
cout << result;
else
cout << "-1";
}
void calcLengths() {
for (int i = 0; i < N; i++)
for (int j = i + 1; j < N; j++)
lengths.push_back({ i, j, power((field[i].first - field[j].first)) + power((field[i].second - field[j].second)) });
}
bool kruskal() {
for (int i = 0; i < lengths.size(); i++) {
int f = lengths[i].first, s = lengths[i].second, l = lengths[i].length;
int sp = parent[s], fp = parent[f];
if (l < C)
continue;
if (fp == -1 && sp == -1) {
set<int> t;
t.insert(f);
t.insert(s);
unionset.push_back(t);
parent[f] = unionset.size()-1;
parent[s] = parent[f];
result += l;
}
else if (fp == -1) {
unionset[sp].insert(f);
parent[f] = sp;
result += l;
}
else if (sp == -1) {
unionset[fp].insert(s);
parent[s] = fp;
result += l;
}
else if(fp != sp) {
for (auto iter = unionset[sp].begin(); iter != unionset[sp].end(); iter++) {
parent[*iter] = fp;
unionset[fp].insert(*iter);
}
result += l;
unionset[sp].clear();
}
}
int root = parent[0];
for (int i = 0; i < N; i++) {
if (parent[i] != root)
return false;
}
return true;
}