最小生成树
- Prim:算法思路OK,但没刷对应的题目
- kruskal:打了几个板子题目
今晚上有手撸了下板子代码,使用优先队列做了优化,提交上去,性能提升不明显,有些小郁闷。。。
明天打算开始先学习强连通【Tarjan】,把这些基础算法学完了,在强化刷题。
题目
- P1546 [USACO3.1]最短网络 Agri-Net
- https://www.luogu.com.cn/problem/P1546
小码匠
代码
代码语言:javascript复制#include <bits/stdc .h>
using namespace std;
#define endl 'n';
struct edge {
int weight;
int from;
int to;
};
struct cmp {
bool operator() (const edge &a, const edge &b) {
return a.weight > b.weight;
}
};
struct UF {
vector<int> fa;
UF (int n) :
fa(n) {}
void initialize (int n) {
for (int i = 0; i < n; i) {
fa[i] = i;
}
}
int find(int a) {
if (a != fa[a]) {
fa[a] = find(fa[a]);
}
return fa[a];
}
void unite(int x, int y) {
int a = find(x);
int b = find(y);
if (a != b) {
fa[b] = a;
}
}
bool is_same(int x, int y) {
return find(x) == find(y);
}
};
void best_coder() {
int n;
cin >> n;
priority_queue <edge, vector<edge>, cmp> g;
UF uf(n);
uf.initialize(n);
for (int i = 0; i < n; i) {
for (int j = 0; j < n; j) {
int a;
cin >> a;
if (j <= i) {
continue;
}
g.push({a, i, j});
}
}
int ans = 0;
while (!g.empty()) {
int a = g.top().from;
int b = g.top().to;
if (uf.is_same(a, b)) {
g.pop();
continue;
}
uf.unite(a, b);
ans = g.top().weight;
g.pop();
}
cout << ans;
}
void happy_coder() {
}
int main() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// 小码匠
best_coder();
// 最优解
// happy_coder();
// 返回
return 0;
}