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;
};

Download