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

#include<iostream>
#include<algorithm>
#include<cstring>
#define fr(a,b,c) for(a=b;a<=c;a++)
using namespace std;

int n,k,sm,re,d[222],a[222][222];

void dfs(int x,int val)
{
    int i;
    d[x]=1;
    fr(i,1,n)
      if (!d[i] && a[x][i]<val) dfs(i,val); 
}

int main()
{
    int i,j;
    cin >> n >> k;
    fr(i,1,n) fr(j,1,n) cin >> a[i][j];
    int l=0,r=32767;
    while (l<=r)
    {
       int m=(l+r)/2;
       memset(d,0,sizeof(d));
       sm=0;
       fr(i,1,n)
         if (!d[i]) dfs(i,m),sm++;
       if (sm>=k)
       {
           re=m; l=m+1;
       }
       else r=m-1;  
    }
    cout << re << endl;
    return 0;
}

Code mẫu của ladpro98

#include <iostream>
#include <cstdio>
#include <algorithm>
const int N = 222;
using namespace std;
int a[N][N];
int n, k;

struct disjoint_set {
    int lab[N];
    disjoint_set()
        {for(int i = 1; i <= n; i++) lab[i] = 0;}
    int root(int u)
        {return lab[u] <= 0 ? u : (lab[u] = root(lab[u]));}
    void join(int u, int v)
        {if (lab[u] > lab[v]) swap(u, v); if (lab[u] == lab[v]) lab[u]--; lab[v] = u;}
};

int cnt(int lim) {
    disjoint_set dsu;
    int cc = n;
    for(int i = 1; i <= n; i++)
    for(int j = i + 1; j <= n; j++)
    if (a[i][j] < lim) {
        int x = dsu.root(i), y = dsu.root(j);
        if (x != y) {
            dsu.join(x, y);
            cc--;
        }
    }
    return cc;
}

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n >> k;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            cin >> a[i][j];
    int l = 0, r = 1 << 16, m, res = 0;
    while (l <= r) {
        m = l + r >> 1;
        if (cnt(m) >= k) {
            res = m;
            l = m + 1;
        }
        else
            r = m - 1;
    }
    cout << res;
    return 0;   
}

Code mẫu của RR

{$R+,Q+}
PROGRAM YUGI;
CONST
  FINP='';
  FOUT='';
  maxn=200;
  maxm=20000;
  oo=1000000;
VAR
  c:array[1..maxn,1..maxn] of longint;
  hu,hv:array[1..maxm] of longint;
  eu,ev,father:array[1..maxn] of longint;
  n,k,hsize:longint;
procedure swap(var a,b:longint);
var
  temp:longint;
begin
  temp:=a; a:=b; b:=temp;
end;
procedure downHeap(i:longint);
var
  j:longint;
begin
  j:=i shl 1;
  while j<=hsize do
    begin
      if (j<hsize) and (c[hu[j+1],hv[j+1]]<c[hu[j],hv[j]]) then inc(j);
      if (c[hu[j],hv[j]]<c[hu[i],hv[i]]) then
        begin
          swap(hu[j],hu[i]);
          swap(hv[j],hv[i]);
        end;
      i:=j; j:=i shl 1;
    end;
end;
procedure upHeap(i:longint);
var
  j:longint;
begin
  j:=i shr 1;
  while (j>=1) and (c[hu[j],hv[j]]>c[hu[i],hv[i]]) do
    begin
      swap(hu[i],hu[j]);
      swap(hv[i],hv[j]);
      i:=j; j:=i shr 1;
    end;
end;
procedure push(u,v:longint);
begin
  inc(hsize);
  hu[hsize]:=u; hv[hsize]:=v;
  upHeap(hsize);
end;
procedure pop(var u,v:longint);
begin
  u:=hu[1]; v:=hv[1];
  swap(hu[hsize],hu[1]);
  swap(hv[hsize],hv[1]);
  dec(hsize);
  downHeap(1);
end;
procedure readInput;
var
  f:text;
  i,j:longint;
begin
  assign(f,FINP); reset(f);
  readln(f,n,k);
  for i:=1 to n do
    for j:=1 to n do
      begin
        read(f,c[i,j]);
        if i<j then push(i,j);
      end;
  close(f);
end;
function getRoot(u:longint):longint;
begin
  while father[u]>0 do u:=father[u];
  getRoot:=u;
end;
procedure union(r1,r2:longint);
var
  x:longint;
begin
  x:=father[r1]+father[r2];
  if father[r1]<father[r2] then
    begin
      father[r2]:=r1;
      father[r1]:=x;
    end
  else
    begin
      father[r1]:=r2;
      father[r2]:=x;
    end;
end;
procedure Kruskal;
var
  i,r1,r2,u,v,count:longint;
begin
  for i:=1 to n do
    father[i]:=-1;
  count:=0;
  while hsize>0 do
    begin
      pop(u,v);
      r1:=getRoot(u);
      r2:=getRoot(v);
      if r1<>r2 then
        begin
          inc(count);
          eu[count]:=u; ev[count]:=v;
          if count=n-1 then exit;
          union(r1,r2);
        end;
    end;
end;
function min(a,b:longint):longint;
begin
  if a<b then min:=a else min:=b;
end;
procedure writeOutput;
var
  ans,i:longint;
  f:text;
begin
  assign(f,FOUT); rewrite(f);
  ans:=oo;
  for i:=n-1 downto n-k+1 do
    ans:=min(ans,c[eu[i],ev[i]]);
  writeln(f,ans);
  close(f);
end;
BEGIN
  readInput;
  Kruskal;
  writeOutput;
END.

Code mẫu của ll931110

#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <fstream>
#include <iostream>
#include <map>
#include <set>
#include <sstream>
#include <stack>
#include <queue>
#include <vector>
#include <utility>
using namespace std;

int a[202][202];
bool chs[202];
int n,k;

bool ok(int x)
{
    memset(chs,false,sizeof(chs));
    int gr = 0;
    for (int i = 1; i <= n; i++) if (!chs[i])
    {
        gr++; if (gr == k) return true;
        chs[i] = true;
        queue<int> q;  q.push(i);
        while (!q.empty())
        {
            int u = q.front();  q.pop();
            for (int v = 1; v <= n; v++)
              if (!chs[v] && a[u][v] < x)
              {
                    chs[v] = true;  q.push(v);
                };
        };
    };
    return false;
};

int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++) scanf("%d", &a[i][j]);
    int inf = 0;  int sup = 32767;  int ret = 0;
    while (inf <= sup)
    {
        int med = (inf + sup) / 2;
        if (ok(med))
        {
            ret = med;  inf = med + 1;
        }
        else sup = med - 1;
    };
    printf("%d\n", ret);
};