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='';
      maxn=10010;
      maxm=100010;
var re,n,m:longint;
    b:array[0..maxm,0..2] of longint;
    cha,sl:array[1..maxn] of longint;

procedure rf;
var i,j:longint;
begin
     read(n,m);
     for i:=1 to m do
         for j:=0 to 2 do
             read(b[i,j]);
     for i:=1 to n do
     begin
          cha[i]:=i; sl[i]:=1;
     end;
end;

procedure sort(l,r:longint);
var i,j,x:longint;
begin
     i:=l; j:=r; x:=b[(i+j) shr 1,2];
     repeat
           while b[i,2]>x do i:=i+1;
           while b[j,2]<x do j:=j-1;
           if i<=j then
           begin
                b[0]:=b[i]; b[i]:=b[j]; b[j]:=b[0];
                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 cha[x]=x then find:=x
     else
     begin
          cha[x]:=find(cha[x]);
          find:=cha[x];
     end;
end;

procedure pr;
var i,j,x,y,xx,yy,dem:longint;
begin
     sort(1,m);
     for i:=1 to m do
     begin
          x:=b[i,0]; y:=b[i,1];
          xx:=find(x); yy:=find(y);
          if xx=yy then re:=re+b[i,2]
          else
          begin
               dem:=dem+1;
               if sl[xx]>=sl[yy] then
               begin
                    cha[yy]:=xx;
                    sl[xx]:=sl[xx]+sl[yy];
               end
               else
               begin
                    cha[xx]:=yy;
                    sl[yy]:=sl[yy]+sl[xx];
               end;
               if dem=n-1 then break;
          end;
     end;
     for j:=i+1 to m do re:=re+b[j,2];
     writeln(re);
end;

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

Code mẫu của happyboy99x

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

#define TR(v,i) for(typeof((v).begin())i=(v).begin();i!=(v).end();++i)
const int N = 1e4 + 7;
int n, m, r[N], l[N];
vector<vector<pair<int, int> > > g;
bool vst[N];

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

void enter() {
    scanf("%d%d",&n,&m); g.resize(n);
    for(int i = 0; i < m; ++i) {
        int u, v, w; scanf("%d%d%d",&u,&v,&w);
        g[--u].push_back(make_pair(--v, w));
        g[v].push_back(make_pair(u, w));
    }
}

int dfs(const int &u, vector<pair<int, pair<int, int> > > &edge, int &sumEdge) {
    int res = 1; vst[u] = true;
    TR(g[u], it) {
        int v = it->first, w = it->second;
        if(!vst[v]) {
            edge.push_back(make_pair(w, make_pair(u, v)));
            sumEdge += w; l[v] = l[u] + 1;
            res += dfs(v, edge, sumEdge);
        } else if(l[v] < l[u] - 1) {
            edge.push_back(make_pair(w, make_pair(u, v)));
            sumEdge += w;
        }
    }
    return res;
}

void solve() {
    int res = 0; initSet(n);
    for(int u = 0; u < n; ++u) if(!vst[u]) {
        vector<pair<int, pair<int, int> > > edge; l[u] = 0;
        int n = dfs(u, edge, res), cnt = 1;
        sort(edge.begin(), edge.end(), greater<pair<int, pair<int, int> > >());
        TR(edge, it) {
            int u = it->second.first, v = it->second.second, w = it->first;
            if(getSet(u) != getSet(v)) {
                res -= w;
                r[r[u]] = r[v];
                if(++cnt == n) break;
            }
        }
    }
    printf("%d\n", res);
}

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

Code mẫu của ladpro98

{$MODE OBJFPC}
program nkracing;
uses    math;
type    e=record
        x,y,w:longint;
        end;
const   maxn=10004;
        maxm=100005;
        fi='';
var     res,n,m:longint;
        a:array[1..maxm] of e;
        lab:array[1..maxn] of longint;
        check:array[1..maxm] of boolean;

procedure input;
var     inp:text;
        i:longint;
begin
        assign(inp,fi);reset(inp);
        readln(inp,n,m);
        for i:=1 to m do
        readln(inp,a[i].x,a[i].y,a[i].w);
        close(inp);
end;

procedure sort(l,r:longint);
var     p,i,j:longint;
        t:e;
begin
        if l>=r then exit;
        i:=l;j:=r;
        p:=a[random(r-l+1)+l].w;
        repeat
                while a[i].w>p do inc(i);
                while a[j].w<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(l,j);sort(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;

procedure kruskal;
var     i,x,y,c:longint;
begin
        sort(1,m);
        for i:=1 to m do
        begin
                x:=root(a[i].x);
                y:=root(a[i].y);
                if x<>y then
                begin
                        inc(c);
                        check[i]:=true;
                        union(x,y);
                end;
                if c=n-1 then break;
        end;
        for i:=1 to m do if not check[i] then inc(res,a[i].w);
end;

begin
        input;
        kruskal;
        write(res);
end.

Code mẫu của RR

//Wishing myself a happy lunar new year with a lot of accept solutions
//Written by Nguyen Thanh Trung
{$R-,Q-}
const
  FINP='';
  FOUT='';
  MAXN=10000;
  MAXM=100000;
var
  m,n,sum,mst:longint;
  eu,ev,ec:array[1..MAXM] of longint;
  father:array[1..MAXN] of longint;
procedure inp; inline;
var
  f:text;
  i:longint;
begin
  assign(f,FINP); reset(f);
  read(f,n,m);
  for i:=1 to m do
    read(f,eu[i],ev[i],ec[i]);
  sum:=0;
  for i:=1 to m do inc(sum,ec[i]);
  close(f);
end;
procedure ans; inline;
var
  f:text;
begin
  assign(f,FOUT); rewrite(f);
  writeln(f,sum-mst);
  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[i+random(j-i+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;
function getRoot(u:longint):longint; inline;
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); inline;
begin
  if father[r1]<father[r2] then
    begin
      father[r1]:=father[r1]+father[r2];
      father[r2]:=r1;
    end
  else
    begin
      father[r2]:=father[r1]+father[r2];
      father[r1]:=r2;
    end;
end;
procedure solve; inline;
var
  i,sc,u,v,r1,r2:longint;
begin
  for i:=1 to n do father[i]:=-1;
  sort(1,m); sc:=0; mst:=0;
  for i:=1 to m do
    begin
      u:=eu[i]; v:=ev[i];
      r1:=getRoot(u);
      r2:=getRoot(v);
      if r1=r2 then continue;
      union(r1,r2);
      inc(sc); inc(mst,ec[i]);
      if sc=n-1 then break;
    end;
end;
begin
  inp;
  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=0,u[20001];
    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);
        minimumCost = minimumCost + v[i].cost;
        v[i].cost = -v[i].cost;
    }
    //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);
   // getch();
}

Code mẫu của ll931110

{$MODE DELPHI}
program NKRACING;
const
  input  = '';
  output = '';
  maxn = 10000;
  maxe = 1000000;
var
  n,e: integer;
  u,v,cost: array[1..maxe] of integer;
  pr,rank: array[1..maxn] of integer;
  tot,tree: integer;

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

  readln(f, n, e);
  tot := 0;
  for i := 1 to e do
    begin
      readln(f, u[i], v[i], cost[i]);
      tot := tot + cost[i];
    end;

  close(f);
end;

procedure sw(var x,y: integer);
var
  z: integer;
begin
  z := x;  x := y;  y := z;
end;

procedure swap(i,j: integer);
begin
  sw(u[i],u[j]);  sw(v[i],v[j]);  sw(cost[i],cost[j]);
end;

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

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

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

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

procedure link(x,y: integer);
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 solve;
var
  i,nedge: integer;
begin
  tree := 0;
  for i := 1 to n do
    begin
      pr[i] := i;
      rank[i] := 0;
    end;

  nedge := 0;
  for i := 1 to e do
    if root(u[i]) <> root(v[i]) then
      begin
        tree := tree + cost[i];
        inc(nedge);
        link(root(u[i]),root(v[i]));
      end;
end;

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

begin
  init;
  sort(1,e);
  solve;
  printresult;
end.

Code mẫu của skyvn97

#include<cstdio>
#include<algorithm>
#define MAX   100100
using namespace std;
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 {
        if (c>x.c) return (true);
        if (c<x.c) return (false);
        return (u+v<x.u+x.v);
    }
};
int m,n;
edge lst[MAX];
int up[MAX];
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 loadgraph(void) {
    scanf("%d",&n);
    scanf("%d",&m);
    int i,u,v,c;
    for (i=1;i<=n;i=i+1) up[i]=-1;
    for (i=1;i<=m;i=i+1) {
        scanf("%d",&u);
        scanf("%d",&v);
        scanf("%d",&c);
        lst[i]=edge(u,v,c);
    }
    sort(&lst[1],&lst[m+1]);
}
void kruskal(void) {
    int i;
    int res=0;
    for (i=1;i<=m;i=i+1) {  
        if (find(lst[i].u)!=find(lst[i].v)) join(lst[i].u,lst[i].v);
        else res+=lst[i].c;
    }
    printf("%d",res);
}
int main(void) {
    loadgraph();
    kruskal();
    return 0;
}

Code mẫu của khuc_tuan

#include <iostream>
#include <cstdio>

using namespace std;

int n, m;
pair<int, pair<int,int> > a[100010];
int F[10010], result;

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);
    memset( F, -1, sizeof(F));
    for(int i=m-1;i>=0;--i) {
        int c = a[i].first;
        int u = a[i].second.first;
        int v = a[i].second.second;
        result += c;
        while(F[u]>=0) u = F[u];
        while(F[v]>=0) v = F[v];
        //cout << c << endl;
        if(u==v) continue;
        result -= c;
        if(F[u]>=F[v]) swap( u, v);
        F[u] += F[v];
        F[v] = u;
    }
    cout << result << endl;
    //system("pause");
    return 0;
}