Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

const fi='';
      fo='';
      maxn=100010;
type ar=array[0..maxn] of longint;
     arr=array[0..2,0..maxn] of longint;
var n:longint;
    nh:array[0..2] of longint;
    a,b,c,x,y,z,par:ar;
    d,h,v:arr;
    re:int64;

procedure rf;
var i:longint;
begin
     read(n);
     for i:=1 to n do
     begin
          read(a[i],b[i],c[i]);
          x[i]:=a[i]; y[i]:=b[i]; z[i]:=c[i];
          d[0,i]:=i; d[1,i]:=i; d[2,i]:=i;
          par[i]:=i;
     end;
end;

procedure sort(var x:ar;z,l,r:longint);
var i,j,t,y:longint;
begin
     i:=l; j:=r; t:=x[(i+j) shr 1];
     repeat
           while x[i]<t do i:=i+1;
           while x[j]>t do j:=j-1;
           if i<=j then
           begin
                y:=x[i]; x[i]:=x[j]; x[j]:=y;
                y:=d[z,i]; d[z,i]:=d[z,j]; d[z,j]:=y;
                i:=i+1; j:=j-1;
           end;
     until i>j;
     if i<r then sort(x,z,i,r);
     if l<j then sort(x,z,l,j);
end;

procedure add(z,x:longint);
var cha,con:longint;
begin
     inc(nh[z]); con:=nh[z];
     cha:=con shr 1;
     while (cha>0) and (v[z,h[z,cha]]>v[z,x]) do
     begin
          h[z,con]:=h[z,cha];
          con:=cha;
          cha:=con shr 1;
     end;
     h[z,con]:=x;
end;

function pop(z:longint):longint;
var x,cha,con:longint;
begin
     pop:=h[z,1];
     x:=h[z,nh[z]]; dec(nh[z]);
     cha:=1; con:=2;
     while con<=nh[z] do
     begin
          if (con<nh[z]) and (v[z,h[z,con+1]]<v[z,h[z,con]]) then inc(con);
          if v[z,x]<=v[z,h[z,con]] then break;
          h[z,cha]:=h[z,con];
          cha:=con;
          con:=cha shl 1;
     end;
     h[z,cha]:=x;
end;

procedure init;
var i:longint;
begin
     for i:=1 to n-1 do
     begin
          v[0,i]:=x[i+1]-x[i];
          v[1,i]:=y[i+1]-y[i];
          v[2,i]:=z[i+1]-z[i];
          add(0,i);
          add(1,i);
          add(2,i);
     end;
end;

function getmin:longint;
begin
     if (v[0,h[0,1]]<=v[1,h[1,1]]) and (v[0,h[0,1]]<=v[2,h[2,1]]) then exit(0)
     else
         if v[1,h[1,1]]<=v[2,h[2,1]] then exit(1)
         else exit(2);
end;

function find(x:longint):longint;
begin
     if x=par[x] then exit(x)
     else
     begin
          par[x]:=find(par[x]);
          exit(par[x]);
     end;
end;

procedure pr;
var i,t,u,p,q:longint;
begin
     sort(x,0,1,n);
     sort(y,1,1,n);
     sort(z,2,1,n);
     init;
     for i:=1 to n-1 do
         while true do
         begin
              t:=getmin;
              u:=pop(t);
              p:=find(d[t,u]); q:=find(d[t,u+1]);
              if p<>q then
              begin
                   re:=re+v[t,u];
                   par[q]:=p;
                   break;
              end;
         end;
     writeln(re);
end;

begin
     assign(input,fi); reset(input);
     rf;
     pr;
     close(input);
end.

Code mẫu của happyboy99x

#include<cstdio>
#include<algorithm>
using namespace std;

const int N = 100000 + 2;
struct empire {
    int x, y, z, id;
    int distance(const empire &o) {
        return min(abs(x - o.x), min(abs(y - o.y), abs(z - o.z)));
    }
} a[N];
bool x_cmp(const empire &a, const empire &b) { return a.x < b.x; }
bool y_cmp(const empire &a, const empire &b) { return a.y < b.y; }
bool z_cmp(const empire &a, const empire &b) { return a.z < b.z; }

struct edge {
    int u, v, d;
    bool operator < (const edge &o) const { return d < o.d; }
    edge() {}
    edge(int u, int v, int d): u(u), v(v), d(d) {}
} e[3*N];

int p[N], n;
void initSet(int n) { for(int i = 0; i < n; ++i) p[i] = i; }
int getSet(int u) { return p[u] == u ? u : p[u] = getSet(p[u]); }

void enter() {
    scanf("%d", &n);
    for(int i = 0; i < n; ++i) {
        scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].z);
        a[i].id = i;
    }
}

void addEdge(int &nEdge) {
    for(int i = 1; i < n; ++i)
        e[nEdge++] = edge(a[i].id, a[i-1].id, a[i-1].distance(a[i]));
}

void solve() {
    int nEdge = 0;
    sort(a, a+n, x_cmp); addEdge(nEdge);
    sort(a, a+n, y_cmp); addEdge(nEdge);
    sort(a, a+n, z_cmp); addEdge(nEdge);
    sort(e, e + nEdge); initSet(n);
    long long res = 0;
    for(int cnt = 0, i = 0; cnt != n-1; ++i)
        if(getSet(e[i].u) != getSet(e[i].v))
            res += e[i].d, p[p[e[i].u]] = p[e[i].v], ++cnt;
    printf("%lld\n", res);
}

int main() {
    enter();
    solve();
    return 0;
}

Code mẫu của ladpro98

{$MODE OBJFPC}
program vnempire;
uses    math;
const   maxn=100005;
        maxm=6*maxn;
        fi='';
type    e=record
        x,y,w:longint;
        end;
        point =record
        v,p:longint;
        end;
        arr=array[1..maxn] of point;

var     x,y,z:arr;
        inp:text;
        n,m,k,res,i,xx,yy:longint;
        ed:array[1..maxm] of e;
        lab:array[1..maxn] of longint;

procedure sort(var a:arr; l,r:longint);
var     p,i,j:longint;
        t:point;
begin
        if l>=r then exit;
        i:=l;j:=r;
        p:=a[random(r-l+1)+l].v;
        repeat
                while a[i].v<p do inc(i);
                while a[j].v>p do dec(j);
                if i<=j then
                begin
                        if i<j then
                        begin
                                t:=a[i];
                                a[i]:=a[j];
                                a[j]:=t;
                        end;
                        inc(i);dec(j);
                end;
        until i>j;
        sort(a,l,j);sort(a,i,r);
end;

procedure sortE(l,r:longint);
var     p,i,j:longint;
        t:e;
begin
        if l>=r then exit;
        i:=l;j:=r;
        p:=ed[random(r-l+1)+l].w;
        repeat
                while ed[i].w<p do inc(i);
                while ed[j].w>p do dec(j);
                if i<=j then
                begin
                        if i<j then
                        begin
                                t:=ed[i];
                                ed[i]:=ed[j];
                                ed[j]:=t;
                        end;
                        inc(i);
                        dec(j);
                end;
        until i>j;
        sortE(l,j);sortE(i,r);

end;

function root(u:longint):longint;
begin
        if lab[u]<=0 then exit(u);
        result:=root(lab[u]);
        lab[u]:=result;
end;

procedure union(u,v:longint);
begin
        if lab[u]<lab[v] then lab[v]:=u
        else
        begin
                if lab[u]=lab[v] then dec(lab[v]);
                lab[u]:=v;
        end;
end;

begin
        assign(inp,fi);reset(inp);
        readln(inp,n);
        for i:=1 to n do
        begin
                readln(inp,x[i].v,y[i].v,z[i].v);
                x[i].p:=i;y[i].p:=i;z[i].p:=i;
        end;
        sort(x,1,n);sort(y,1,n);sort(z,1,n);
        for i:=2 to n do
        begin
                inc(m);
                ed[m].x:=x[i].p;ed[m].y:=x[i-1].p;ed[m].w:=abs(x[i].v-x[i-1].v);
                inc(m);
                ed[m].x:=y[i].p;ed[m].y:=y[i-1].p;ed[m].w:=abs(y[i].v-y[i-1].v);
                inc(m);
                ed[m].x:=z[i].p;ed[m].y:=z[i-1].p;ed[m].w:=abs(z[i].v-z[i-1].v);
        end;
        sortE(1,m);
        for i:=1 to m do
        begin
                xx:=root(ed[i].x);
                yy:=root(ed[i].y);
                if xx<>yy then
                begin
                        union(xx,yy);
                        inc(res,ed[i].w);
                        inc(k);
                end;
                if k=n-1 then break;
        end;
        write(res);
end.

Code mẫu của RR

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>

#define MAXN 100111
#define oo 1000111000
#define FOR(i,a,b)  for(int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
#define FORV(i,v)   for(typeof(v.begin()) i=v.begin(); i!=v.end(); i++)
#define P pair<int,int>
#define F first
#define S second
#define MP make_pair
#define PB push_back
using namespace std;

int debug=0;
int n,a[MAXN][3],d[MAXN];
vector< P > ke[MAXN];
P c[MAXN];

void inp() {
    scanf("%d",&n);
    FOR(i,1,n)
        FOR(j,0,2) scanf("%d",&a[i][j]);
}

void init() {
    FOR(j,0,2) {
        FOR(i,1,n) {
            c[i].F=a[i][j];
            c[i].S=i;
        }
        sort(c+1,c+n+1);
        FOR(i,1,n) {
            if (i>1) ke[c[i].S].PB(MP(c[i-1].S,c[i].F-c[i-1].F));
            if (i<n) ke[c[i].S].PB(MP(c[i+1].S,c[i+1].F-c[i].F));
        }
    }

    if (debug)
        FOR(i,1,n) {
            FORV(now,ke[i])
                cout<<"("<<now->F<<","<<now->S<<") ";
            cout<<endl;
        }
}

set< P > s;

void modify(int i) {
    FORV(now,ke[i]) {
        int j=now->F, c=now->S;
        if (d[j]<0) continue;
        if (c<d[j]) {
            d[j]=c;
            s.insert(MP(c,j));
        }
    }
}

void solve() {
    FOR(i,1,n) d[i]=oo;
    modify(1); d[1]=-1;
    long long res=0;
    while (!s.empty()) {
        set< P >::iterator it=s.begin();
        int c=it->F, j=it->S; s.erase(it);
        if (c!=d[j]) continue;
        if (d[j]<0) continue;
        d[j]=-1;
        modify(j);
        res+=c;
    }
    cout<<res;
}

int main() {
    inp();
    init();
    solve();
    return 0;
}

Code mẫu của hieult

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iomanip>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned int ui;
typedef unsigned long long ull;

#define Rep(i,n) for(__typeof(n) i = 0; i < (n); ++i)
#define Repd(i,n) for(__typeof(n) i = (n)-1; i >= 0; --i)
#define For(i,a,b) for(__typeof(b) i = (a); i <= (b); ++i)
#define Ford(i,a,b) for(__typeof(a) i = (a); i >= (b); --i)
#define Fit(i,v) for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i)
#define Fitd(i,v) for(__typeof((v).rbegin()) i = (v).rbegin(); i != (v).rend(); ++i)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()
#define ms(a,x) memset(a, x, sizeof(a))
#define nl puts("")
#define sp printf(" ")
#define ok puts("ok")
//#include <conio.h>

template<class F, class T> T convert(F a, int p = -1) { stringstream ss; if (p >= 0) ss << fixed << setprecision(p); ss << a; T r; ss >> r; return r; }
template<class T> void db(T a, int p = -1) { if (p >= 0) cout << fixed << setprecision(p); cout << a << " "; }
template<class T> T gcd(T a, T b) { T r; while (b != 0) { r = a % b; a = b; b = r; } return a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<class T> T sqr(T x) { return x * x; }
template<class T> T cube(T x) { return x * x * x; }
template<class T> struct Triple { T x, y, z; Triple() {} Triple(T _x, T _y, T _z) : x(_x), y(_y), z(_z) {} };
template<class T> Triple<T> euclid(T a, T b) { if (b == 0) return Triple<T>(1, 0, a); Triple<T> r = euclid(b, a % b); return Triple<T>(r.y, r.x - a / b * r.y, r.z); }
template<class T> int getbit(T s, int i) { return (s >> i) & 1; }
template<class T> T onbit(T s, int i) { return s | (T(1) << i); }
template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); }
template<class T> int cntbit(T s) { return s == 0 ? 0 : cntbit(s >> 1) + (s & 1); }
const int bfsz = 1 << 16; char bf[bfsz + 5]; int rsz = 0;int ptr = 0;
char gc() { if (rsz <= 0) { ptr = 0; rsz = fread(bf, 1, bfsz, stdin); if (rsz <= 0) return EOF; } --rsz; return bf[ptr++]; }
void ga(char &c) { c = EOF; while (!isalpha(c)) c = gc(); }
int gs(char s[]) { int l = 0; char c = gc(); while (isspace(c)) c = gc(); while (c != EOF && !isspace(c)) { s[l++] = c; c = gc(); } s[l] = '\0'; return l; }
template<class T> bool gi(T &v) {
    v = 0; char c = gc(); while (c != EOF && c != '-' && !isdigit(c)) c = gc(); if (c == EOF) return false; bool neg = c == '-'; if (neg) c = gc();
    while (isdigit(c)) { v = v * 10 + c - '0'; c = gc(); } if (neg) v = -v; return true;
}

const double PI = 2 * acos(0);
const string months[] = {"January", "February", "March", "April", "May", "June", "July", "August", "September", "October", "November", "December"};
const int days[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
//const int dr[] = {0, 0, -1, +1};
//const int dc[] = {-1, +1, 0, 0};
const int dr[] = {-2, -1, +1, +2, +2, +1, -1, -2};
const int dc[] = {+1, +2, +2, +1, -1, -2, -2, -1};

const int inf = (int)1e9 + 5;
const ll linf = (ll)1e16 + 5;
const double eps = 1e-9;
const ll mod = 1000000000;
typedef pair<int, int> II;

using namespace std;

#define maxn 300005

struct graph{
    int x,y,cost;
    graph(){};
    graph(int _x, int _y, int _cost){
        x = _x; y = _y; cost = _cost;     
    }
    bool operator <(graph const G) const{
        return cost<G.cost;
    }
};

graph v[maxn];
int par[maxn];

int find(int x){
    if(x == par[x]) return x;
    return par[x] = find(par[x]);
}


bool Union(int a,int b){
    int p = find(a);
    int q = find(b);
    if(p == q) return false;
    par[p] = max(p, q); par[q] = max(p, q);
    return true;
}

pair<Triple<int>, int> A[maxn];

bool comx(pair<Triple<int>, int> const &T1, pair<Triple<int>, int> const &T2){ return T1.fi.x < T2.fi.x;}
bool comy(pair<Triple<int>, int> const &T1, pair<Triple<int>, int> const &T2){ return T1.fi.y < T2.fi.y;}
bool comz(pair<Triple<int>, int> const &T1, pair<Triple<int>, int> const &T2){ return T1.fi.z < T2.fi.z;}

int dis(pair<Triple<int>, int> const T1, pair<Triple<int>, int> const T2){
    return min(abs(T1.fi.x - T2.fi.x), min( abs(T1.fi.y - T2.fi.y), abs(T1.fi.z - T2.fi.z)));
}

int main(){

//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
    int n;
    gi(n);
    Rep(i, n) {
        gi(A[i].fi.x); gi(A[i].fi.y); gi(A[i].fi.z); A[i].se = i;
    }

    sort(A, A + n, comx);
    int num = 0;
    Rep(i, n + 1) par[i] = i;
    Rep(i, n - 1){
        v[num++] = graph(A[i].se, A[i + 1].se, dis(A[i], A[i + 1]));
    }
    sort(A, A + n, comy);
    Rep(i, n - 1){
        v[num++] = graph(A[i].se, A[i + 1].se, dis(A[i], A[i + 1]));
    }
    sort(A, A + n, comz);
    Rep(i, n - 1){
        v[num++] = graph(A[i].se, A[i + 1].se, dis(A[i], A[i + 1]));
    }
    sort(v, v + num);
    ll res = 0;
    Rep(i, num){
        if(Union(v[i].x, v[i].y)){
            res += v[i].cost;
        }
    }
    cout << res << endl;
     // getch();
}

Code mẫu của ll931110

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

Code mẫu của khuc_tuan

#include <iostream>
#include <cstdio>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

#define Rep(i,n) for(int i=0;i<(n);++i)
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Ford(i,a,b) for(int i=(a);i>=(b);--i)
#define fi first
#define se second
#define pb push_back
#define MP make_pair

int x[100010],y[100010],z[100010];
int n, ne;
pair<int,int> a[100010],b[100010],c[100010];
pair<int,pair<int,int> > e[300010];
int f[100010];

int getroot(int i){
    if(f[i]<0)return i;else return getroot(f[i]);
}

int main() {
    scanf("%d",&n);
    Rep(i,n){
        scanf("%d%d%d",x+i,y+i,z+i);
        a[i]=make_pair(x[i],i);
        b[i]=make_pair(y[i],i);
        c[i]=make_pair(z[i],i);
    }
    sort(a,a+n);
    sort(b,b+n);
    sort(c,c+n);
    Rep(i,n-1)e[ne++].second=make_pair(a[i].second,a[i+1].second);
    Rep(i,n-1)e[ne++].second=make_pair(b[i].second,b[i+1].second);
    Rep(i,n-1)e[ne++].second=make_pair(c[i].second,c[i+1].second);
    Rep(i,ne)e[i].first=min(min(abs(x[e[i].se.fi]-x[e[i].se.se]),abs(y[e[i].se.fi]-y[e[i].se.se])),abs(z[e[i].se.fi]-z[e[i].se.se]));
    sort(e,e+ne);
    long long res=0;
    memset(f,-1,sizeof(f));
    Rep(i,ne){
        int u=getroot(e[i].se.fi);
        int v=getroot(e[i].se.se);
        if(u!=v){
            res+=e[i].fi;
            if(f[u]<f[v])f[u]+=f[v],f[v]=u;
            else f[v]+=f[u],f[u]=v;
        }
    }
    cout<<res<<endl;
    return 0;   
}