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.