VNEMPIRE - Đế chế
Tác giả: ll931110
Ngôn ngữ: C++
#include <algorithm>
#include <bitset>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cstring>
#include <deque>
#include <fstream>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
typedef long long ll;
using namespace std;
struct edge
{
int u,v,cost;
};
int n;
int x[100010],y[100010],z[100010];
int pre[100010];
int lab[100010];
vector< pair<int,int> > v;
vector<edge> e;
bool cmp(edge q1,edge q2)
{
return (q1.cost < q2.cost);
};
void addedge()
{
sort(v.begin(),v.end());
for (int i = 1; i < v.size(); i++)
{
edge new_edge;
new_edge.u = v[i - 1].second;
new_edge.v = v[i].second;
new_edge.cost = v[i].first - v[i - 1].first;
e.push_back(new_edge);
};
v.clear();
};
void makeset(int k)
{
pre[k] = k; lab[k] = 0;
};
int root(int k)
{
if (k != pre[k]) pre[k] = root(pre[k]);
return pre[k];
};
void connect(int i,int j)
{
int i1 = root(i),j1 = root(j);
if (lab[i1] > lab[j1]) pre[j1] = i1; else pre[i1] = j1;
if (lab[i1] == lab[j1]) lab[j1]++;
};
int main()
{
// freopen("empire.in","r",stdin);
// freopen("empire.ou","w",stdout);
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d %d %d", &x[i], &y[i], &z[i]);
for (int i = 1; i <= n; i++) v.push_back(make_pair(x[i],i));
addedge();
for (int i = 1; i <= n; i++) v.push_back(make_pair(y[i],i));
addedge();
for (int i = 1; i <= n; i++) v.push_back(make_pair(z[i],i));
addedge();
sort(e.begin(),e.end(),cmp);
for (int i = 1; i <= n; i++) makeset(i);
ll ret = 0;
for (int i = 0; i < e.size(); i++)
if (root(e[i].u) != root(e[i].v))
{
connect(e[i].u,e[i].v); ret += e[i].cost;
};
cout << ret << endl;
};