prim.cpp

Bài toán

Tìm cây khung với trọng số bé nhất của đồ thị.

Độ phức tạp

O((m+n)logn)

Code này của Nguyễn Tiến Trung Kiên

#include <stdio.h>

#include <algorithm>

#include <iostream>

#include <queue>

#include <vector>

using namespace std;

typedef pair<int, int> ii;

#define X first

#define Y second

#define N 10004

int n, m;

vector<ii> a[N];

int d[N];

void enter() {

    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));

    }

}

bool minimize(int &a, int b) {

    if (a > b)

        a = b;

    else

        return false;

    return true;

}

int prim(int start) {

    int Answer = 0;

    priority_queue<ii> qu;

    for (int i = 1; i <= n; ++i) d[i] = 0x33334444;

    qu.push(ii(0, start)), d[start] = 0;

    while (qu.size()) {

        ii top = qu.top();

        qu.pop();

        int u = top.Y;

        if (d[u] != -top.X) continue;

        Answer += d[u], d[u] = 0;

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

            int v = a[u][i].Y;

            if (minimize(d[v], a[u][i].X))

                qu.push(ii(-d[v], v));

        }

    }

    return Answer;

}

int main() {

    ios ::sync_with_stdio(false);

    cin >> n >> m;

    enter();

    cout << prim(1) << endl;

    cin.ignore(2);

}

Nhận xét

Trên đồ thị dày, có thể cải tiến độ phức tạp thành O(n2).

Code này đã được dùng để nộp cho một bài trên SPOJ.