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>
#define fr(a,b,c) for(a=b;a<=c;a++)
#define frr(a,b,c) for(a=b;a>=c;a--)
#define maxn 100100
#define oo 1000000
using namespace std;
struct rec{ int x,y,z; };

int n,m,lab[maxn],ok[maxn],sl,p[maxn],e[maxn][18],f[maxn][18],next[maxn];
int a[maxn*2],c[maxn*2],h[maxn],d[maxn],hh;
rec b[maxn];
long long re;

void sort(int l,int r)
{
    int i=l,j=r,x=b[(i+j)/2].z,y;
    do
    {
        while (b[i].z>x) i++;
        while (b[j].z<x) j--;
        if (i<=j) 
        {
           swap(b[i],b[j]);
           i++; j--;
        }
    } while (i<=j);
    if (i<r) sort(i,r);
    if (l<j) sort(l,j); 
}
int get(int x)
{
    if (lab[x]!=x) lab[x]=get(lab[x]);
    return lab[x];
}

void visit(int x,int y)
{
    e[x][0]=y; hh=max(hh,h[x]);
    int i;
    fr(i,p[x]+1,p[x+1])
      if (a[i]!=y)
      {
         h[a[i]]=h[x]+1;
         d[a[i]]=c[i];
         visit(a[i],x);
      }
}

int calc(int x,int y)
{
    int i,lg,res=oo;
    if (h[x]<h[y]) swap(x,y);
    for (lg=0;1<<lg<=h[x];lg++); lg--;
    frr(i,lg,0)
      if (h[x]-(1<<i)>=h[y])
      {
         res=min(res,f[x][i]);
         x=e[x][i];
      }
    if (x==y) return res;
    frr(i,lg,0)
      if (e[x][i] && e[x][i]!=e[y][i])
      {
         res=min(res,min(f[x][i],f[y][i]));
         x=e[x][i]; y=e[y][i];
      }
    res=min(res,min(d[x],d[y]));
    return res;
}

int main()
{
    int i,x,y,j,v=0,w=100001;
    cin >> n >> m;
    fr(i,1,m) scanf("%d%d%d",&b[i].x,&b[i].y,&b[i].z);
    sort(1,m);
    fr(i,1,n) lab[i]=i;
    fr(i,1,m)
    {
       if (sl<n-1) 
       {      
          x=get(b[i].x); y=get(b[i].y);
          if (x!=y)
          {
             ok[i]=1;
             lab[y]=x; 
             p[b[i].x]++; p[b[i].y]++;
             next[v]=i; v=i;
             ++sl;
          }
          else
          {
              next[w]=i; w=i;
          }      
       }
       else
       {
          next[w]=i; w=i;
       } 
    }
    fr(i,2,n+1) p[i]+=p[i-1];
    i=next[0];
    while (i)
    {
       a[p[b[i].x]]=b[i].y;
       c[p[b[i].x]--]=b[i].z;
       a[p[b[i].y]]=b[i].x;
       c[p[b[i].y]--]=b[i].z;
       i=next[i];
    }
    visit(1,0);
    d[1]=oo;
    fr(i,1,n) f[i][0]=d[i];
    for (j=1;1<<j<=hh;j++)
      fr(i,1,n)
        if (e[i][j-1])
        {
           e[i][j]=e[e[i][j-1]][j-1];
           f[i][j]=min(f[i][j-1],f[e[i][j-1]][j-1]); 
        }
        else f[i][j]=oo;
    i=next[100001];
    while (i)
    {
        re+=calc(b[i].x,b[i].y)-b[i].z; 
        i=next[i];
    }
    cout << re << endl;
    return 0;
}

Code mẫu của happyboy99x

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

#define TR(v,i) for(__typeof((v).begin())i=(v).begin();i!=(v).end();++i)
const int N = 1e5, LOG = 17, INF = 1e9;
vector<vector<pair<int, int> > > mst;
vector<pair<int, pair<int, int> > > edge;
int n, m, mindist[N][LOG], par[N][LOG], sett[N], h[N], logn;

void initSet() {
    for(int i = 0; i < n; ++i)
        sett[i] = i;
}

int getSet(int u) {
    return u == sett[u] ? u : sett[u] = getSet(sett[u]);
}

void enter() {
    cin >> n >> m;
    mst.resize(n);
    for(int i = 0; i < m; ++i) {
        int u, v, c; cin >> u >> v >> c;
        edge.push_back(make_pair(-c, make_pair(--u, --v)));
    }
}

void findMST() {
    initSet();
    sort(edge.begin(), edge.end());
    TR(edge, it) {
        int u = it->second.first, v = it->second.second, w = -it->first;
        if(getSet(u) != getSet(v)) {
            mst[u].push_back(make_pair(v, w));
            mst[v].push_back(make_pair(u, w));
            sett[sett[u]] = sett[v];
        }
    }
}

void dfs(int u) {
    TR(mst[u], it) {
        int v = it->first, w = it->second;
        if(v != par[u][0]) {
            h[v] = h[u] + 1;
            par[v][0] = u;
            mindist[v][0] = w;
            dfs(v);
        }
    }
}

void initLCA() {
    logn = 0; while(1 << logn <= n) ++logn; --logn;
    for(int j = 1; 1 << j < n; ++j)
        for(int i = 0; i < n; ++i)
            if(par[i][j-1] != -1) {
                par[i][j] = par[par[i][j-1]][j-1];
                mindist[i][j] = min(mindist[i][j-1], mindist[par[i][j-1]][j-1]);
            }
}

int getmin(int u, int v) {
    if(h[u] < h[v]) swap(u, v);
    int res = INF;
    for(int j = logn; j >= 0; --j)
        if(h[u] - (1 << j) >= h[v]) {
            res = min(res, mindist[u][j]);
            u = par[u][j];
        }
    if(u == v) return res;
    for(int j = logn; j >= 0; --j)
        if(par[u][j] != par[v][j]) {
            res = min(res, min(mindist[u][j], mindist[v][j]));
            u = par[u][j];
            v = par[v][j];
        }
    return min(res, min(mindist[u][0], mindist[v][0]));
}

void solve() {
    long long res = 0;
    TR(edge, it) {
        int u = it->second.first, v = it->second.second, w = it->first;
        res += getmin(u, v) + w;
    }
    cout << res << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    enter();
    findMST();
    memset(par, -1, sizeof par); h[0] = 0;
    dfs(0);
    initLCA();
    solve();
    return 0;
}

Code mẫu của ladpro98

{$MODE OBJFPC}
program upgranet;
uses    math;
type    e=record
        x,y,w:longint;
        end;
        e2=record
        v,w:longint;
        end;
const   fi='';
        maxn=100005;
        maxm=200005;
        maxL=trunc(ln(maxn)/ln(2))+1;
var     n,m,log,me:longint;
        a:array[1..maxm] of e;
        adj:array[1..maxm] of e2;
        link:array[1..maxm] of longint;
        lab,head,par,w,d:array[0..maxn] of longint;
        b,mi:array[0..maxn,0..maxL] of longint;
        choose,check:array[1..maxn] 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
                        union(x,y);
                        inc(c);
                        choose[i]:=true;
                        inc(me);
                        adj[me].v:=y;
                        adj[me].w:=a[i].w;
                        link[me]:=head[x];
                        head[x]:=me;
                        inc(me);
                        adj[me].v:=x;
                        adj[me].w:=a[i].w;
                        link[me]:=head[y];
                        head[y]:=me;
                end;
                if c=n-1 then break;
        end;
end;

procedure dfs(i,p,c:longint);
var     j:longint;
begin
        par[i]:=p;
        d[i]:=d[p]+1;
        w[i]:=c;
        check[i]:=true;
        j:=head[i];
        while j>0 do
        begin
                if not check[adj[j].v] then
                dfs(adj[j].v,i,adj[j].w);
                j:=link[j];
        end;
end;

procedure initLCA;
var     i,j:longint;
begin
        log:=trunc(ln(n)/ln(2))+1;
        for i:=0 to n do
        begin
                b[i,0]:=par[i];
                mi[i,0]:=w[i];
        end;
        for j:=1 to log do
        for i:=0 to n do
        begin
                b[i,j]:=b[b[i,j-1],j-1];
                mi[i,j]:=min(mi[i,j-1],mi[b[i,j-1],j-1]);
        end;
end;

function getbit(i,j:longint):longint;
begin
        exit(i shr (j-1) and 1);
end;

function lca(u,v:longint):longint;
var     i,res,t:longint;
begin
        res:=high(longint);
        if d[u]>=d[v] then
        begin
                if d[u]>d[v] then
                begin
                        t:=d[u]-d[v];
                        for i:=log downto 1 do
                        if getbit(t,i)=1 then
                        begin
                                res:=min(res,mi[u,i-1]);
                                u:=b[u,i-1];
                        end;
                end;
                if u=v then exit(res);
                for i:=log downto 0 do
                begin
                        if b[u,i]<>b[v,i] then
                        begin
                                res:=min(res,mi[u,i]);
                                res:=min(res,mi[v,i]);
                                u:=b[u,i];
                                v:=b[v,i];
                        end;
                        if b[u,0]=b[v,0] then res:=min(res,min(mi[u,0],mi[v,0]));
                end;
                exit(res);
        end
        else exit(lca(v,u));
end;

procedure output;
var     i:longint;
        res:int64;
begin
        res:=0;
        for i:=1 to m do
        if not choose[i] then
        inc(res,lca(a[i].x,a[i].y)-a[i].w);
        write(res);
end;

begin
        input;
        kruskal;
        dfs(1,0,0);
        initLCA;
        output;
end.

Code mẫu của RR

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <deque>
#include <complex>

#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
#define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
#define ll long long
#define F first
#define S second
#define PB push_back
#define MP make_pair
using namespace std;

const double PI = acos(-1.0);

//Buffer reading
int INP,AM;
#define BUFSIZE (1<<10)
char BUF[BUFSIZE+1], *inp=BUF;
#define GETCHAR(INP) { \
    if(!*inp) { \
        fread(BUF,1,BUFSIZE,stdin); \
        inp=BUF; \
    } \
    INP=*inp++; \
}
#define DIG(a) (((a)>='0')&&((a)<='9'))
#define GN(j) { \
    AM=0;\
    GETCHAR(INP); while(!DIG(INP) && INP!='-') GETCHAR(INP);\
    if (INP=='-') {AM=1;GETCHAR(INP);} \
    j=INP-'0'; GETCHAR(INP); \
    while(DIG(INP)){j=10*j+(INP-'0');GETCHAR(INP);} \
    if (AM) j=-j;\
}
//End of buffer reading

int n, m, lab[100111];
pair< int, pair<int,int> > e[100111];
vector<pair<int,int> > ke[100111];

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

void merge(int u, int v) {
    int x = lab[u] + lab[v];
    if (lab[u] < lab[v]) {
        lab[u] = x;
        lab[v] = u;
    }
    else {
        lab[v] = x;
        lab[u] = v;
    }
}

int father[22][100111], nn[22][100111], d[100111];

void dfs(int u, int fu) {
    REP(i,ke[u].size()) {
        int v = ke[u][i].F;
        if (v == fu) continue;
        father[0][v] = u;
        nn[0][v] = ke[u][i].S;
        d[v] = d[u] + 1;
        dfs(v, u);
    }
}

void init() {
    FOR(i,1,20)
        FOR(u,1,n) {
            int v = father[i-1][u];
            if (v != -1) {
                father[i][u] = father[i-1][v];
                nn[i][u] = min(nn[i-1][u], nn[i-1][v]);
            }
        }
}

int get(int u, int v) {
    if (u == v) return 0;
    if (d[u] < d[v]) swap(u,v);
    int res = 1000111000;

    FORD(i,20,0)
    if (father[i][u] >= 0 && d[father[i][u]] >= d[v]) {
        res = min(res, nn[i][u]);
        u = father[i][u];
    }
    if (u == v) return res;

    FORD(i,20,0)
        if (father[i][u] != father[i][v]) {
            res = min(res, nn[i][u]);
            res = min(res, nn[i][v]);
            u = father[i][u];
            v = father[i][v];
        }

    res = min(res, nn[0][u]);
    res = min(res, nn[0][v]);

    return res;
}

bool mst[100111];

int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    GN(n); GN(m);
    REP(i,m) {
        GN(e[i].S.F);
        GN(e[i].S.S);
        GN(e[i].F);
    }
    sort(e, e+m);

    memset(lab, -1, sizeof lab);
    FORD(i,m-1,0) {
        int u = e[i].S.F, v = e[i].S.S, c = e[i].F;
        u = getRoot(u); v = getRoot(v);
        if (u == v) continue;
        merge(u, v);
        u = e[i].S.F, v = e[i].S.S;
        ke[u].PB(MP(v,c));
        ke[v].PB(MP(u,c));
        mst[i] = true;
    }
//    cout << endl;

    memset(father, -1, sizeof father);
    dfs(1, -1);
    init();

    ll res = 0;

    FORD(i,m-1,0)
    if (!mst[i]) {
        int u = e[i].S.F, v = e[i].S.S;
//        cout << u << ' ' << v << ' ' << get(u,v) << endl;
        res += get(u, v) - e[i].F;
    }

    cout << res << endl;
    return 0;
}

Code mẫu của skyvn97

#include<algorithm>
#include<cstdio>
#include<iostream>
#include<queue>
#include<vector>
#define MAX   100100
#define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1)
#define FORD(i,b,a) for (int i=(b);i>=(a);i=i-1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
#define fi   first
#define se   second
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> pii;
const int INF=(int)1e9+7;
pii e[MAX];
bool mst[MAX];
vector<ii> g[MAX];
ii p[MAX][19];
int h[MAX];
class DSU {
    private:
    vector<int> lab;
    int find(int x) {
        if (lab[x]<0) return (x);
        lab[x]=find(lab[x]);
        return (lab[x]);
    }
    public:
    DSU() {
        lab=vector<int>();
    }
    DSU(int _n) {
        lab=vector<int>(_n+7,-1);
    }
    bool join(int a,int b) {
        int x=find(a);
        int y=find(b);
        if (x==y) return (false);
        lab[y]=x;
        return (true);
    }
};
DSU dsu;
int m,n;
void loadgraph(void) {
    scanf("%d",&n);
    scanf("%d",&m);
    FOR(i,1,m) {
        int u,v,w;
        scanf("%d",&u);
        scanf("%d",&v);
        scanf("%d",&w);
        e[i]=pii(w,ii(u,v));
    }
    dsu=DSU(n);
    h[0]=-1;
}
void loadtree(void) {
    sort(e+1,e+m+1,greater<pii>());
    FOR(i,1,m) {
        if (dsu.join(e[i].se.fi,e[i].se.se)) {
            int u=e[i].se.fi;
            int v=e[i].se.se;
            int w=e[i].fi;
            g[u].push_back(ii(v,w));
            g[v].push_back(ii(u,w));
        }
        else (mst[i]=true);
    }
}
void visit(int u) {
    FORE(it,g[u]) if (it->fi!=p[u][0].fi) {
        int v=it->fi;
        p[v][0]=ii(u,it->se);
        h[v]=h[u]+1;
        visit(v);
    }
}
void setupLCA(void) {
    visit(1);
    FOR(j,1,18) FOR(i,1,n)
        p[i][j]=ii(p[p[i][j-1].fi][j-1].fi,min(p[i][j-1].se,p[p[i][j-1].fi][j-1].se));
}
int mindis(int u,int v)  {
    if (h[u]<h[v]) return (mindis(v,u));
    int ret=INF;
    FORD(j,18,0) if (h[p[u][j].fi]>=h[v]) {
        ret=min(ret,p[u][j].se);
        u=p[u][j].fi;
    }
    if (u==v) return (ret);
    FORD(j,18,0) if (p[u][j].fi!=p[v][j].fi) {
        ret=min(ret,p[u][j].se);
        ret=min(ret,p[v][j].se);
        u=p[u][j].fi;
        v=p[v][j].fi;       
    }
    ret=min(ret,p[u][0].se);
    ret=min(ret,p[v][0].se);
    return (ret);
}
void process(void) {
    long long res=0;
    FOR(i,1,m) if (mst[i]) {
        int u=e[i].se.fi;
        int v=e[i].se.se;
        int w=e[i].fi;
        res+=mindis(u,v)-w;
    }
    cout << res;
}
int main(void) {
    loadgraph();
    loadtree();
    setupLCA();
    process();
    return 0;
}