HỌC TIN CÙNG THỦ KHOA

Mời các bạn Download code tại: Click here

1. File Input: Click here

- Dòng đầu tiên gồm 2 số n và m tương ứng là số đỉnh và số cạnh của đồ thị.

- m dòng tiếp theo mỗi dòng gồm 3 số là u, v, c tương ứng là đỉnh đầu, đỉnh cuối và trọng số của một cạnh của đồ thị

2. File Output

- Gồm nhiều dòng, mỗi dòng 2 số u, v tương ứng là đỉnh đầu và đỉnh cuối của cạnh nằm trong cây khung nhỏ nhất.

- Dòng cuối cùng ghi trọng số của cây khung nhỏ nhất tìm được.

#include <fstream>
#include <string.h>

#define fi "KRUSKAL.INP"
#define fo "KRUSKAL.OUT"

const int MAXN = 10000;
const int MAXM = 1000;
/// #define MAXN 10000

using namespace std;


struct Canh {
    int dinhdau, dinhcuoi;
    int dodai;
};

int n, m;
Canh a[MAXM];
int father[MAXN];

fstream f;

void Nhap() {
    f.open(fi, ios::in);
    f >> n >> m;
    int i, j;
    for (i=1; i <= m; i++) f >> a[i].dinhdau >> a[i].dinhcuoi >> a[i].dodai;
    f.close();
}

void SapXep() {
    Canh tg;
    int i, j;
    for (i=1; i<=m-1; i++)
        for (j=i+1; j <= m; j++)
            if (a[i].dodai > a[j].dodai) {
                    tg = a[i];
                    a[i] = a[j];
                    a[j] = tg;
            }
}

int root(int x) {
    if (father[x] == -1) return x;
        else return root(father[x]);
}

void hopnhat(int r1, int r2) { /// r1 khac r2
    if (r1 < r2) father[r2] = r1;
        else /// r1 > r2
            father[r1] = r2;
}

void Kruskal() {
    SapXep();
    int i;
    for (i=1; i <= n; i++) father[i] = -1;
    int dem = 0;
    int tong = 0;
    int x, y;
    int r1, r2;
    f.open(fo, ios::out);
    for (i=1; i <= m; i++) {
        if (dem == n-1) break;
        x = a[i].dinhdau;
        y = a[i].dinhcuoi;

        r1 = root(x);
        r2 = root(y);

        if (r1 != r2) {
            f << x << "   " << y << endl; /// end line
            dem++;
            tong = tong + a[i].dodai;
            hopnhat(r1, r2);
        }
    }
    f << "Tong trong so cua cay khung be nhat la: " << tong;
    f.close();

}



int main() {
    Nhap();
    Kruskal();
}