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

var n,m,i,j,x,y,re:longint;
    a,b,c,d:array[1..15555] of longint;

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

function find(x:longint):longint;
begin
     if x<>d[x] then d[x]:=find(d[x]);
     exit(d[x]);
end;

begin
     read(n,m);
     for i:=1 to n do d[i]:=i;
     for i:=1 to m do read(a[i],b[i],c[i]);
     sort(1,m);
     for i:=1 to m do
     begin
          x:=find(a[i]); y:=find(b[i]);
          if x<>y then
          begin
               d[y]:=x;
               dec(n); re:=re+c[i];
               if n=1 then
               begin
                    writeln(re); halt;
               end;
          end;
     end;
end.

Code mẫu của happyboy99x

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

typedef pair<int, int> ii;
typedef pair<int, ii> i3;
#define fi first
#define se second

int n, m;
vector<i3> g;
int r[10005];

int getr( int u ) {
    return u == r[u] ? u : r[u] = getr(r[u]);
}

int main() {
    scanf( "%d%d", &n, &m );
    for( int i = 0; i < m; ++i ) {
        int u, v, l; scanf( "%d%d%d", &u, &v, &l );
        g.push_back(i3(l, ii(--u, --v)));
    }
    sort(g.begin(), g.end());
    for( int i = 0; i < n; ++i ) r[i] = i;
    int c = 0, res = 0;
    for( typeof(g.begin()) it = g.begin(), _e = g.end(); c != n-1 && it != _e; ++it ) {
        int u = it->se.fi, v = it->se.se, l = it->fi;
        if (getr(u) != getr(v)) {
            res += l; ++c;
            r[r[u]] = r[v];
        }
    }
    printf( "%d\n", res );
    return 0;
}

Code mẫu của ladpro98

//http://vn.spoj.com/problems/QBMST/
#include <bits/stdc++.h>
#define ii pair<int, int>
#define iii pair<int, ii>
#define X first
#define Y second
const int N = 10050;
const int M = 15050;
using namespace std;
int n, m;
int lab[N];
iii e[M];

int root(int u) {
    if (lab[u] <= 0) return u;
    return lab[u] = root(lab[u]);
}

void unite(int u, int v) {
    if (lab[u] < lab[v]) lab[v] = u;
    else {
        if (lab[u] == lab[v]) lab[v]--;
        lab[u] = v;
    }
}

int main()
{
    scanf("%d %d", &n, &m);
    int i, x, y, cnt = 0, res = 0;
    for(i = 1; i <= m; i++)
        scanf("%d %d %d", &e[i].Y.X, &e[i].Y.Y, &e[i].X);
    sort(e + 1, e + 1 + m);
    for(i = 1; i <= m; i++) {
        x = root(e[i].Y.X); y = root(e[i].Y.Y);
        if (x != y) {
            unite(x, y);
            res += e[i].X;
            cnt++;
        }
        if (cnt == n - 1) break;
    }
    printf("%d", res);
    return 0;
}

Code mẫu của RR

var
  u,v,res,i,n,m:longint;
  lab,eu,ev,ec:array[1..15111] of longint;

procedure swap(var a,b:longint);
    var
      tmp:longint;
    begin
      tmp:=a; a:=b; b:=tmp;
    end;

procedure sort(l,r:longint);
    var
      i,j,mid:longint;
    begin
      i:=l; j:=r; mid:=ec[l+random(r-l+1)];
      repeat
        while ec[i]<mid do inc(i);
        while ec[j]>mid do dec(j);
        if i<=j then
          begin
            swap(eu[i],eu[j]);
            swap(ev[i],ev[j]);
            swap(ec[i],ec[j]);
            inc(i); dec(j);
          end;
      until i>j;
      if i<r then sort(i,r);
      if l<j then sort(l,j);
    end;

procedure union(r1,r2:longint);
    var
      x:longint;
    begin
      x:=lab[r1]+lab[r2];
      if lab[r1]<lab[r2] then
        begin
          lab[r1]:=x;
          lab[r2]:=r1;
        end
      else
        begin
          lab[r2]:=x;
          lab[r1]:=r2;
        end;
    end;

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

begin
  read(n,m);
  for i:=1 to m do
    read(eu[i],ev[i],ec[i]);

  sort(1,m);
  for i:=1 to n do lab[i]:=-1;
  for i:=1 to m do
    begin
      u:=getRoot(eu[i]);
      v:=getRoot(ev[i]);
      if u<>v then
        begin
          union(u,v);
          inc(res,ec[i]);
        end;
    end;
  writeln(res);
end.

Code mẫu của hieult

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
//#include <conio.h>

using namespace std;

#define MAX(a,b) ((a>b)?a:b)
#define CLEAR(A,N) (memset(A,0,(N)*sizeof(A[0])))

const int maxEdgeSize = 200005;
typedef struct{
        int x,y,cost;
}graph;

graph v[maxEdgeSize];
int ar[maxEdgeSize];

int findSet(int i){
    while(ar[i]!=i)
        i = ar[i];
    return i;
}

void makeUnion(int a,int p1,int b, int p2){
     int x = MAX(p1,p2);
     ar[a] = x;
     ar[b] = x;
     ar[p1] = x;
     ar[p2] = x;
}

int adjustUsingUnionFind(int a,int b)
{
    if(ar[a] == -1)  ar[a] = a;
    if(ar[b] == -1)  ar[b] = b;
    int p1 = findSet(a);
    int p2 = findSet(b);
    if(p1!=p2){
          makeUnion(a,p1,b,p2);
          return 1;
          }
    else return 0;
}

bool operator < (graph a, graph b)
{
     return a.cost < b.cost;
}

int main()
{
    //freopen("QBMST.in","r",stdin);
    int m,n,i,minimumCost;
    scanf("%d %d",&m,&n);
    for(int i = 0;i<n;i++)
        scanf("%d %d %d",&v[i].x,&v[i].y,&v[i].cost);
    sort(v,v+n);
    for(int i = 0;i<=m;i++)
        ar[i] = -1;
    minimumCost = 0;
    for(int i = 0;i<n;i++)
    {

         if(adjustUsingUnionFind(v[i].x,v[i].y)==1)
         {
              minimumCost+= v[i].cost;
              //printf("%d\n",v[i].cost);
         }
    }
    printf("%d",minimumCost);
    //getch();
}

Code mẫu của ll931110

Program QBMST;
        Const
                input  = '';
                output = '';
                  maxn = 10000;
                  maxm = 15000;
                  maxc = 1000000000;
        Type
                arrn = array[0..maxn + 1] of longint;
                arrm = array[1..maxm + 1] of longint;
                 arr = array[0..2 * maxm + 1] of longint;
               check = array[1..maxn] of boolean;
        Var
                      x,y,c: arrm;
              h,adj,adjcost: arr;
           d,trace,heap,pos: arrn;
                  n,m,nHeap: longint;
                       free: check;

Procedure LoadGraph;
          Var
                f: text;
                i: longint;
          Begin
                Assign(f, input);
                        Reset(f);

                Fillchar(h, sizeof(h), 0);
                Readln(f, n, m);

                For i:= 1 to m do
                  Begin
                        Readln(f, x[i], y[i], c[i]);
                        inc(h[x[i]]);
                        inc(h[y[i]]);
                  End;

                Close(f);

                For i:= 2 to n do h[i]:= h[i] + h[i - 1];
                For i:= 1 to m do
                  Begin
                        adj[h[x[i]]]:= y[i];
                        adjcost[h[x[i]]]:= c[i];
                        dec(h[x[i]]);

                        adj[h[y[i]]]:= x[i];
                        adjcost[h[y[i]]]:= c[i];
                        dec(h[y[i]]);
                  End;

                h[n + 1]:= 2 * m;
          End;

Procedure init;
          Var
                i: integer;
          Begin
                d[1]:= 0;
                For i:= 2 to n do d[i]:= maxc;

                Fillchar(pos, sizeof(pos), 0);
                Fillchar(free, sizeof(free), true);
                Fillchar(trace, sizeof(trace), 0);

                nHeap:= 0;
          End;

Procedure Update(v: longint);
          Var
                parent,child: longint;
          Begin
                child:= pos[v];
                If child = 0 then
                  Begin
                        inc(nHeap);
                        child:= nHeap;
                  End;

                parent:= child div 2;
                While (parent > 0) and (d[heap[parent]] > d[v]) do
                  Begin
                        heap[child]:= heap[parent];
                        pos[heap[child]]:= child;

                        child:= parent;
                        parent:= child div 2;
                  End;

                heap[child]:= v;
                pos[v]:= child;
          End;

Function pop: longint;
         Var
                r,c,v: longint;
         Begin
                pop:= heap[1];
                v:= heap[nHeap];
                dec(nHeap);

                r:= 1;
                While r * 2 <= nHeap do
                  Begin
                        c:= r * 2;
                        If (c < nHeap) and (d[heap[c]] > d[heap[c + 1]]) then inc(c);
                        If d[v] <= d[heap[c]] then break;

                        heap[r]:= heap[c];
                        pos[heap[r]]:= r;

                        r:= c;
                  End;

                heap[r]:= v;
                pos[v]:= r;
         End;

Procedure Prim;
          Var
                i,u,v,iv: longint;
          Begin
                Update(1);
                Repeat
                        u:= pop;
                        free[u]:= false;

                        For iv:= h[u] + 1 to h[u + 1] do
                          Begin
                                v:= adj[iv];
                                If free[v] and (d[v] > adjcost[iv]) then
                                  Begin
                                        d[v]:= adjcost[iv];
                                        trace[v]:= u;
                                        update(v);
                                  End;
                          End;
                Until nHeap = 0;
          End;

Procedure printresult;
          Var
                         f: text;
                u,v,iv,res: longint;
          Begin
                Assign(f, output);
                        Rewrite(f);

                res:= 0;
                For u:= 2 to n do
                    For iv:= h[u] + 1 to h[u + 1] do
                        Begin
                                v:= adj[iv];
                                If v = trace[u] then
                                  Begin
                                        res:= res + adjcost[iv];
                                        break;
                                  End;
                        End;

                    Writeln(f, res);
                Close(f);
          End;

Begin
        LoadGraph;
        init;
        Prim;
        printresult;
End.

Code mẫu của skyvn97

#include<cstdio>
#include<algorithm>
#define MAX   15151
using namespace std;
struct edge {
    int u,v,w;
    bool operator < (const edge &x) const {
        if (w<x.w) return (true);
        if (w>x.w) return (false);
        return (u+v<x.u+x.v);
    }
};
int up[MAX];
edge e[MAX];
int m,n;
void init(void) {
    scanf("%d",&n);
    scanf("%d",&m);
    int i;
    for (i=1;i<=m;i=i+1) {
        scanf("%d",&e[i].u);
        scanf("%d",&e[i].v);
        scanf("%d",&e[i].w);
    }
    for (i=1;i<=n;i=i+1) up[i]=-1;
    sort(&e[1],&e[m+1]);
}
int find(int x) {
    if (up[x]<0) return (x);
    up[x]=find(up[x]);
    return (up[x]);
}
void join(int a,int b) {
    int x=find(a);
    int y=find(b);
    if (x==y) return;
    up[y]=x;
}
void kruskal(void) {
    int i,c,s;
    c=0;s=0;
    for (i=1;i<=m;i=i+1) {
        if (find(e[i].u)!=find(e[i].v)) {
            join(e[i].u,e[i].v);
            c=c+1;
            s=s+e[i].w;
            if (c==n-1) {
                printf("%d",s);
                return;
            }
        }
    }
}
int main(void) {
    init();
    kruskal();
    return 0;
}

Code mẫu của khuc_tuan

#include <stdio.h>
#include <iostream>
using namespace std;

int n, m, f[15000];
pair<int, pair<int,int> > a[16600];

int getroot(int i) { return (f[i]<0) ? i : getroot(f[i]); }

void merge(int i, int j) {
    i = getroot(i);
    j = getroot(j);
    if(f[i]>f[j]) swap(i,j);
    f[i] += f[j];
    f[j] = i;
}

int main() {
    scanf("%d%d", &n, &m);
    for(int i=0;i<m;++i) scanf("%d%d%d", &a[i].second.first, &a[i].second.second, &a[i].first);
    sort( a, a+m);
    int res = 0;
    memset( f, -1, sizeof(f));
    for(int i=0;i<m;++i) {
        int u = a[i].second.first;
        int v = a[i].second.second;
        if(getroot(u)!=getroot(v)) {
            merge(u,v);
            res += a[i].first;
        }
    }
    printf("%d\n", res);
    return 0;
}