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

uses math;
const fi='';
var m,n,re:longint;
    cha,sl:array[1..1000] of longint;
    a,b,c:array[1..10000] of longint;

procedure rf;
var i:longint;
begin
      read(n,m);
      for i:=1 to m do read(a[i],b[i],c[i]);
end;

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:=c[i]; c[i]:=c[j]; c[j]:=y;
                   y:=a[i]; a[i]:=a[j]; a[j]:=y;
                   y:=b[i]; b[i]:=b[j]; b[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 cha[x]=x then find:=x
        else
        begin
                cha[x]:=find(cha[x]);
                find:=cha[x];
        end;
end;

procedure pr;
var i,x,y,dem:longint;
begin
     sort(1,m);
     for i:=1 to n do
     begin
        cha[i]:=i; sl[i]:=1;
     end;
     dem:=0; i:=0;
     repeat
           i:=i+1;
           x:=find(a[i]); y:=find(b[i]);
           if x<>y then
           begin
                inc(dem);
                if sl[x]>sl[y] then
                begin
                     cha[y]:=x;
                     sl[x]:=sl[x]+sl[y];
                end
                else
                begin
                     cha[x]:=y;
                     sl[y]:=sl[y]+sl[x];
                end;
           end;
     until dem=n-1;
     writeln(c[i]);
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;

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

int r[1005];
i3 g[10005];
int n, m;

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

int main() {
    scanf( "%d%d", &n, &m );
    for( int i = 0; i < m; ++i ) {
        scanf( "%d%d%d", &g[i].se.fi, &g[i].se.se, &g[i].fi );
        --g[i].se.fi; --g[i].se.se;
    }
    for( int i = 0; i < n; ++i ) r[i] = i;
    sort(g, g+m);
    int numE = 0, res;
    for( int i = 0; i < m && numE < n; ++i ) {
        int l = g[i].fi, u = g[i].se.fi, v = g[i].se.se;
        if (getRoot(u) != getRoot(v)) {
            res = l;
            r[r[u]] = r[v];
            ++numE;
        }
    }
    printf( "%d\n", res );
    return 0;
}

Code mẫu của ladpro98

program nkcity;
uses    math;
type    e=record
        v,w,link:longint;
        end;
const   fi='';
        maxm=23456;
        maxn=2345;

var     adj:array[1..maxm] of e;
        head:array[1..maxn] of longint;
        avail:array[1..maxn] of boolean;
        q:array[1..maxm] of longint;
        n,m,mm,maxW,res:longint;

procedure input;
var     inp:text;
        i,x,y,w:longint;
begin
        assign(inp,fi);
        reset(inp);
        readln(inp,n,mm);
        for i:=1 to mm do
        begin
                readln(inp,x,y,w);
                inc(m);
                adj[m].v:=y;
                adj[m].w:=w;
                adj[m].link:=head[x];
                head[x]:=m;
                inc(m);
                adj[m].v:=x;
                adj[m].w:=w;
                adj[m].link:=head[y];
                head[y]:=m;
                maxW:=max(maxW,w);
        end;
        close(inp);
end;

function bfs(lim:longint):boolean;
var     l,r,i,u:longint;
begin
        for i:=1 to n do
        avail[i]:=true;
        l:=1;r:=1;
        q[1]:=1;avail[1]:=false;
        while l<=r do
        begin
                u:=q[l];inc(l);
                i:=head[u];
                while i>0 do
                begin
                        if (adj[i].w<=lim) and (avail[adj[i].v]) then
                        begin
                                inc(r);
                                q[r]:=adj[i].v;
                                avail[adj[i].v]:=false;
                        end;
                        i:=adj[i].link;
                end;
        end;
        for i:=1 to n do
        if avail[i] then exit(false);
        exit(true);
end;

procedure process;
var     l,r,m:longint;
begin
        l:=1;r:=maxW;
        while l<=r do
        begin
                m:=(l+r) div 2;
                if bfs(m) then
                begin
                        res:=m;
                        r:=m-1;
                end
                else    l:=m+1;
        end;
end;

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

Code mẫu của RR

uses math;
var
  res,u,v,i,n,m:longint;
  eu,ev,ec:array[1..10111] of longint;
  lab:array[1..10111] 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;

function getRoot(u:longint):longint;
    begin
      if lab[u]<0 then exit(u);
      lab[u]:=getRoot(lab[u]); exit(lab[u]);
    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;

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
          res:=max(res,ec[i]);
          union(u,v);
        end;
    end;
  writeln(res);
end.

Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>
#define maxn 1001
#define oo 100000000

int n,m,a[maxn][maxn],d[maxn],flag[maxn],x,y,z;

int min(int a,int b)
{
    if(a<b) return a;
    else return b;
}

int main()
{
   //freopen("NKCITY.in","r",stdin);
    scanf("%d %d",&n,&m);
    for(int i = 1;i<=n;i++)
    {
        d[i] = oo;
        flag[i] = 0;
        for(int j = 1;j<=n;j++)
            a[i][j] = oo;
    }
    for(int i = 1;i<=m;i++)
    {
        scanf("%d %d %d",&x,&y,&z);
        a[x][y] = z;
        a[y][x] = z;
    }
    for(int i = 1;i<=n;i++)
        d[i]= a[1][i];
    int KQ = 0,u=1;flag[1] = 1;d[1]=0;
    while(true)
    {

               //printf("1");
        int fl = 0, minn = oo;
        for(int i = 1;i<=n;i++)
        {
            if(flag[i]==0 && d[i]<minn)
            {
                fl = i;
                minn = d[i];
            }
        }
        if(fl==0)
             break;
        else
        {
            u = fl;
            flag[u] = 1;
            if(d[fl]>KQ)
                KQ = d[fl];
            for(int i = 1;i<=n;i++)
                d[i] = min(d[i],a[fl][i]);
        }
    }
    printf("%d",KQ);
   // getch();
}

Code mẫu của ll931110

{$MODE DELPHI}
Program NKCITY;
        Const
                input  = '';
                output = '';
        Var
                c: array[1..1000,1..1000] of integer;
                d: array[1..1000] of integer;
             free: array[1..1000] of boolean;
              n,m: integer;

Procedure LoadGraph;
          Var
                        f: text;
                  i,j,u,v: integer;
          Begin
                Assign(f, input);
                        Reset(f);
                        Readln(f, n, m);

                For u:= 1 to n do
                  For v:= 1 to n do
                    if u = v then c[u,v]:= 0 else c[u,v]:= 1000000000;

                For i:= 1 to m do
                    Begin
                        Readln(f, u, v, c[u,v]);
                        c[v,u]:= c[u,v];
                    End;

                Close(f);
          End;

Procedure Prim;
          Var
                          f: text;
                     maxlen: integer;
                u,i,min,v,k: integer;
          Begin
                d[1]:= 0;
                For i:= 2 to n do d[i]:= 1000000000;
                maxlen:= 0;

                FIllchar(free, sizeof(free), true);

                For k:= 1 to n do
                    Begin
                        u:= 0;
                        min:= 1000000000;

                        For i:= 1 to n do
                                if free[i] and (d[i] < min) then
                                        Begin
                                                u:= i;
                                                min:= d[i];
                                        End;
                        If maxlen < min then maxlen:= min;

                        free[u]:= false;
                        For v:= 1 to n do
                            If free[v] and (d[v] > c[u,v])
                                       then d[v]:= c[u,v];
                    End;

                Assign(f, output);
                        Rewrite(f);
                        Writeln(f, maxlen);
                Close(f);
          End;

Begin
        LoadGraph;
        Prim;
End.

Code mẫu của skyvn97

#include<cstdio>
#include<algorithm>
#define MAX   10101
using namespace std;
struct edge {
    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];
int m,n;
edge e[MAX];
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 process(void) {
    int i,c;
    c=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;
            if (c==n-1) {
                printf("%d",e[i].w);
                return;
            }
        }
    }
}
int main(void) {
    init();
    process();
    return 0;
}

Code mẫu của khuc_tuan

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<pair<int, pair<int,int> > > vec;
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i=0;i<m ;++i) {
        int u, v, c;
        scanf("%d%d%d", &u, &v, &c);
        vec.push_back( make_pair( c, make_pair( u, v)));
    }
    int f[n+1], res = 0;
    memset( f, -1, sizeof(int) * (n+1));
    sort( vec.begin(), vec.end());
    for(int i=0;i<vec.size();++i) {
        int u = vec[i].second.first;
        int v = vec[i].second.second;
        int c = vec[i].first;
        while(f[u]>=0) u = f[u];
        while(f[v]>=0) v = f[v]; 
        if(u!=v) {
            res = c;
            f[u] += f[v];
            f[v] = u;
        }
    }
    printf("%d\n", res);
    return 0;
}