Tìm cây bao trùm nhỏ nhất

Bài toán:

Cho đơn đồ thị vô hướng liên thông G = (V, E) gồm n đỉnh và m cạnh, các đỉnh được đánh số từ 1 tới n và các cạnh được đánh số từ 1 tới m. Hãy tìm cây khung nhỏ nhất của đồ thị G

Input

Dòng 1: Chứa hai số n, m (1 <= n <= 10000; 1 <= m <= 15000)

M dòng tiếp theo, dòng thứ i có dạng ba số nguyên u, v, c. Trong đó (u, v) là chỉ số hai đỉnh đầu mút của cạnh thứ i và c trọng số của cạnh đó (1 <= u, v <= n; 0 <= c <= 10000).

Output

Dòng đầu là tổng trọng số của cây khung nhỏ nhất
Sau là các cạnh
Sử dụng 2 thuật toán prim và kruscal

Example

Input:

9 8
7 3 9267
9 4 8261
9 9 189
5 4 6042
1 1 9771
1 9 2765
6 3 9054
6 2 9532

Output:

17068
4 9 8261
5 4 6042
9 1 2765
kruscal
44921
1 9 2765
5 4 6042
9 4 8261
6 3 9054
7 3 9267
6 2 9532

#include<bits/stdc++.h>
using namespace std;

typedef pair<int, int> ii;
#define oo 100000000
#define maxn 1004

int n, m;
vector<ii> a[maxn];
vector <pair<int ,pair<int ,int> > > save_canh;

int d[maxn];

int trace[maxn];
int aa[maxn][maxn];
int sinhtest()
{
    srand(time(NULL));
    string filein = "input.txt";
    ofstream myfile;
    myfile.open (filein);
    int n = rand()%10 +1;
    myfile << n << " ";
    int m = rand()%(n*(n-1)/2) + 1;
    myfile << m << endl;

    for(int i = 1; i<= n ;i++)
        for(int j= 1; j<= n; j++) aa[i][j] = 0;

    for(int i= 1; i<= m ;i++)
    {
        int x, y , w;

        do
        {
            x = rand()%n +1;
            y = rand()%n + 1;
            w = rand()%10000 + 1;

        }while(aa[x][y] != 0 or aa[y][x] != 0);
        aa[x][y] = w;
        myfile << x << " " << y <<  " " << w << endl;
    }



    myfile.close();
}

int prim(int start){
    int Answer=0;
    priority_queue<ii> qu;
    for(int i= 1; i <= n; i++ ) d[i]=oo, trace[i] = 0;
    qu.push(ii(0,start)), d[start]=0;

    while (qu.size()){
        ii top=qu.top(); qu.pop();
        int u=top.second;
        if (d[u]!=-top.first) continue;
        Answer+=d[u], d[u]=0;

        for (int i=0; i < a[u].size(); i++)
        {
            int v = a[u][i].second;

            if (d[v] >  a[u][i].first)
            {
                d[v] =a[u][i].first;
                trace[v] = u;
                qu.push(ii(-d[v], v));
            }
        }
    }
    return Answer;
}



//


int cha[maxn], rankList[maxn];
int check[maxn];

void init() {
    for (int i=0; i<maxn; i++) {
        cha[i] = i;
        rankList[i] = 0;
    }
}

int findList(int u) {
    if (cha[u] != u) cha[u] = findList(cha[u]);
    return cha[u];
}

void join(int u, int v) {
    u = findList(u);
    v = findList(v);
    if (u == v) return;
    if (rankList[u] == rankList[v]) rankList[u]++;
    if (rankList[u] < rankList[v]) cha[u] = v;
    else cha[v] = u;
}




//
int main(){
    sinhtest();
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    cin >> n >> m;
    for(int i= 1; i<= m; i++){
        int p, q, w;
        cin >> p >> q >> w;
        a[p].push_back(ii(w, q));
        a[q].push_back(ii(w, p));
        save_canh.push_back(make_pair(w, make_pair(p, q)));
    }


    int ans = prim(1);
    cout << ans << endl;

    for(int i= 1; i<= n; i++)
    {
        for(int j=  0; j< a[i].size(); j++)
        if (a[i][j].second  == trace[i]) {
            cout << i << " " << trace[i] << " " << a[i][j].first << endl;
            break;
        }
    }

    cout << "kruscal" << endl;
    sort(save_canh.begin(), save_canh.end());
    init();

    ans = 0;
    int i;
    for (int i= 0; i< save_canh.size(); i++){
        check[i] = 0;
        if (findList(save_canh[i].second.first) != findList(save_canh[i].second.second)){
            join(save_canh[i].second.first, save_canh[i].second.second);
            ans += save_canh[i].first;
            check[i]= 1;
        }
    }

    cout << ans << endl;
    for(int i= 0; i < save_canh.size(); i++ )
    if (check[i])cout << save_canh[i].second.first << " " << save_canh[i].second.second << " " << save_canh[i].first << endl;


}

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Đăng xuất /  Thay đổi )

Google photo

Bạn đang bình luận bằng tài khoản Google Đăng xuất /  Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất /  Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất /  Thay đổi )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.