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 ladpro98

#include <bits/stdc++.h>
#define ii pair<int, int>
#define iii pair<int, ii>
#define X first
#define Y second
const int N = 10100;
const int M = 100010;
using namespace std;
int lab[N], C[N];
iii e[M];
int n, m;

int root(int u) 
    {return (lab[u] <= 0) ? u : (lab[u] = root(lab[u]));}
void unite(int u, int v) 
    {if (lab[u] > lab[v]) swap(u, v); if (lab[u] == lab[v]) lab[u]--; lab[v] = u;}

int main() {
    ios :: sync_with_stdio(0); cin.tie();
    cin >> n >> m;
    int u, v, L;
    for(int i = 1; i <= n; i++) cin >> C[i];
    for(int i = 1; i <= m; i++) {
        cin >> u >> v >> L;
        e[i] = iii(C[u] + C[v] + L + L, ii(u, v));
    }
    sort(e + 1, e + 1 + m);
    int cnt = 0, res = *min_element(C + 1, C + 1 + n);
    for(int i = 1; i <= m; i++) {
        u = root(e[i].Y.X); 
        v = root(e[i].Y.Y);
        if (u != v) {
            res += e[i].X;
            unite(u, v);
            cnt++;
        }
        if (cnt == n - 1) break;
    }
    cout << res << endl;
    return 0;
}

Code mẫu của RR

{
PROG: cheer
LANG: PASCAL
ID: invinci3
}
const
  FINP='';
  FOUT='';
  MAXN=10011;
  MAXM=100011;
var
  cost,father:array[1..MAXN] of longint;
  eu,ev,ec:array[1..MAXM] of longint;
  kq,n,m:longint;
procedure inp;
var
  f:text;
  i,u,v,c:longint;
begin
  assign(f,FINP); reset(f);
  read(f,n,m);
  kq:=maxlongint;
  for i:=1 to n do
    begin
      read(f,cost[i]);
      if kq>cost[i] then kq:=cost[i];
    end;
  for i:=1 to m do
    begin
      read(f,u,v,c);
      eu[i]:=u; ev[i]:=v;
      ec[i]:=2*c+cost[u]+cost[v];
    end;
  close(f);
end;
procedure swap(var a,b:longint); inline;
var
  temp:longint;
begin
  temp:=a; a:=b; b:=temp;
end;
procedure sort(l,r:longint); inline;
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 ans;
var
  f:text;
begin
  assign(f,FOUT); rewrite(f);
  writeln(f,kq);
  close(f);
end;
function getRoot(u:longint):longint;
begin
  if father[u]<0 then getRoot:=u
  else begin father[u]:=getRoot(father[u]); getRoot:=father[u]; end;
end;
procedure union(r1,r2:longint);
var
  x:longint;
begin
  x:=father[r1]+father[r2];
  if father[r1]<father[r2] then
    begin
      father[r1]:=x;
      father[r2]:=r1;
    end
  else
    begin
      father[r2]:=x;
      father[r1]:=r2;
    end;
end;
procedure solve;
var
  i,count,r1,r2:longint;
begin
  for i:=1 to n do father[i]:=-1;
  count:=0;
  for i:=1 to m do
    begin
      r1:=getRoot(eu[i]); r2:=getRoot(ev[i]);
      if r1=r2 then continue;
      inc(count); inc(kq,ec[i]);
      if count=n-1 then break;
      union(r1,r2);
    end;
end;
begin
  inp;
  sort(1,m);
  solve;
  ans;
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,minn = 1000000,u[20001];
    scanf("%d %d",&m,&n);
    for(int i = 1;i<=m;i++)
    {
        scanf("%d",&u[i]);
        if(u[i]<minn)
            minn = u[i];
    }
   // printf("1");
    for(int i = 0;i<n;i++)
    {
        scanf("%d %d %d",&v[i].x,&v[i].y,&v[i].cost);
        v[i].cost = 2*v[i].cost+u[v[i].x]+u[v[i].y];
    }
    //printf("2");
    sort(v,v+n);
    for(int i = 0;i<=m;i++)
        ar[i] = -1;
    minimumCost = 0;
   // printf("3");
    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+minn);
    //getch();
}

Code mẫu của ll931110

program CHEER;
const
  input  = '';
  output = '';
  maxn = 10000;
  maxp = 100000;
type
  edge = record
    u,v,cost: longint;
  end;
var
  e: array[1..maxp] of edge;
  a,pr,rank: array[1..maxn] of longint;
  n,p: longint;
  res: longint;

procedure init;
var
  f: text;
  i: longint;
begin
  assign(f, input);
    reset(f);

  readln(f, n, p);
  for i := 1 to n do read(f, a[i]);

  for i := 1 to p do
    begin
      read(f, e[i].u, e[i].v, e[i].cost);
      e[i].cost := 2 * e[i].cost + a[e[i].u] + a[e[i].v];
    end;

  close(f);
end;

procedure swap(var x,y: edge);
var
  z: edge;
begin
  z := x;  x := y;  y := z;
end;

procedure sort(l,h: longint);
var
  i,j: longint;
  t: longint;
begin
  if l >= h then exit;
  i := l;  j := h;  t := e[random(h - l + 1) + l].cost;

  repeat
    while e[i].cost < t do inc(i);
    while e[j].cost > t do dec(j);
    if i <= j then
      begin
        if i < j then swap(e[i],e[j]);
        inc(i);
        dec(j);
      end;
  until i > j;

  sort(l,j);  sort(i,h);
end;

procedure makeset(i: longint);
begin
  pr[i] := i;
  rank[i] := 0;
end;

function root(x: longint): longint;
begin
  if x <> pr[x] then pr[x] := root(pr[x]);
  root := pr[x];
end;

procedure link(x,y: longint);
begin
  if rank[x] > rank[y] then pr[y] := x else pr[x] := y;
  if rank[x] = rank[y] then inc(rank[y]);
end;

procedure union(x,y: longint);
begin
  link(root(x),root(y));
end;

procedure Kruskal;
var
  i,cc: longint;
begin
  cc := 0;
  res := 0;
  for i := 1 to n do
    if (res = 0) or (res > a[i]) then res := a[i];

  for i := 1 to n do makeset(i);

  for i := 1 to p do
    begin
      if cc = n - 1 then break;
      if root(e[i].u) <> root(e[i].v) then
        begin
          res := res + e[i].cost;
          union(e[i].u,e[i].v);
          inc(cc);
        end;
    end;
end;

procedure printresult;
var
  f: text;
begin
  assign(f, output);
    rewrite(f);
    writeln(f, res);
  close(f);
end;

begin
  init;
  sort(1,p);
  Kruskal;
  printresult;
end.

Code mẫu của skyvn97

#include<bits/stdc++.h>
#define MAXV   10101
#define MAXE   200200
using namespace std;
typedef long long ll;
struct edge {
    int u,v,c;
    edge(){}
    edge(const int &_u,const int &_v,const int &_c) {
        u=_u;v=_v;c=_c;
    }
    bool operator < (const edge &x) const {
        return (c<x.c);
    }
};
int t[MAXV];
int up[MAXV];
edge g[MAXE];
int n,m,mv;
int min(const int &x,const int &y) {
    if (x<y) return (x); else return (y);
}
int find(const int &x) {
    if (up[x]<0) return (x);
    up[x]=find(up[x]);
    return (up[x]);
}
void join(const int &a,const int &b) {
    int x=find(a);
    int y=find(b);
    if (x==y) return;
    up[y]=x;
}
void loadgraph(void) {
    scanf("%d",&n);
    scanf("%d",&m);
    int i,u,v,c;
    mv=(int)1e9;
    for (i=1;i<=n;i=i+1) {
        scanf("%d",&t[i]);
        mv=min(mv,t[i]);
    }
    for (i=1;i<=m;i=i+1) {
        scanf("%d",&u);
        scanf("%d",&v);
        scanf("%d",&c);
        g[i]=edge(u,v,2*c+t[u]+t[v]);
    }   
    sort(&g[1],&g[m+1]);
    //for (i=1;i<=m;i=i+1) printf("%d %d %d\n",g[i].u,g[i].v,g[i].c);
}
void kruskal(void) {
    int i;
    ll res=(ll)mv;  
    for (i=0;i<=n;i=i+1) up[i]=-1;
    for (i=1;i<=m;i=i+1)
        if (find(g[i].u)!=find(g[i].v)) {
            //printf("Accept %d %d %d\n",g[i].u,g[i].v,g[i].c);
            res+=g[i].c;
            join(g[i].u,g[i].v);
        }   
    printf("%lld",res);
}
int main(void) {
    //freopen("tmp.txt","r",stdin);
    loadgraph();
    kruskal();
    return 0;
}