Prim and Kruskal
#include <iostream>
#include <algorithm>
#define r() fast_read()
#define f(inc, frm, to) for (size_t inc = frm; inc < to; ++inc)
using namespace std;
using ll = long long int;
const int N = 1E2 + 1E1;
const int oo = 0x7f7f7f7f;
inline ll fast_read(void) {
ll n = 0, sign = 1;
char c = getchar();
while (c < 48 or c > 57) {
if (c == '-') sign = ~0;
c = getchar();
}
while (c >= 48 and c <= 57) {
n = (n << 1) + (n << 3) + (c ^ 48);
c = getchar();
}
return sign * n;
}
// ================== 并查集(UnionFind -- Disjoint Set)数据结构 ================== //
struct UF {
public:
UF(const int n) : counts_(n) {
f(i, 0, n) p_[i] = i;
}
int find(int x) {
if (p_[x] ^ x) p_[x] = find(p_[x]);
return p_[x];
}
bool unite(int p, int q) {
int root_p = find(p), root_q = find(q);
if (root_p == root_q) return false;
p_[root_p] = root_q;
--counts_;
return true;
}
int get_counts() const { return counts_; }
private:
int counts_;
int p_[N];
};
// ================== 并查集(UnionFind -- Disjoint Set)数据结构 ================== //
// ================== 图的边集数组表示法 ================== //
int edge_cnt;
struct Edge {
int u, v, w;
bool operator<(const Edge& other) const {
return w < other.w;
}
} edges[N * N]; // 如果输入是完全图: 边数 m = n * (n - 1) / 2
// ================== 图的边集数组表示法 ================== //
int n;
int adj[N][N]; // 邻接矩阵
inline void print_adj(void) {
f(u, 0, n) f(v, 0, n) printf("%-2d%c", *(*(adj + u) + v), v == n - 1 ? 10 : 32);
putchar(10);
}
// 集合避圈法
// Time Complexity: O(N^2)
// Conclusion: Prim 在算法实现上像极了Dijkstra
inline int prim(void) {
int lowcost[N]; // 到U集合最邻近点的边权
bool s[N] = { false };
s[0] = 1; // 将0号节点加入U集合
f(u, 0, n) lowcost[u] = adj[0][u];
f(i, 0, n - 1) {
// 寻找U集合到V-U集合边权最小值 (这条边所对应的是V-U集合中的端点t)
int min_cost = oo, t;
f(u, 0, n)
if (not s[u] and lowcost[u] < min_cost) {
min_cost = lowcost[u];
t = u;
}
s[t] = 1; // 将t节点加入U集合
// 更新
f(u, 0, n)
if (not s[u] and adj[t][u] < lowcost[u])
lowcost[u] = adj[t][u];
}
// f(u, 0, n) printf("%d%c", lowcost[u], u == n - 1 ? 10 : 32);
int tot_cost = 0;
f(u, 0, n) tot_cost += lowcost[u];
return tot_cost;
}
inline int kruskal(void) {
sort(edges, edges + edge_cnt);
UF uf(n);
int tot_cost = 0, cnt = 0;
f(e, 0, edge_cnt) {
int u = edges[e].u, v = edges[e].v, w = edges[e].w;
if (not uf.unite(u, v)) continue;
tot_cost += w;
if (++cnt == n - 1) return tot_cost;
}
return 0;
}
// Prim
signed main(int argc, char const *argv[]) {
// freopen("test.in", "r", stdin);
while (scanf("%d", &n) != EOF) {
f(u, 0, n) f(v, 0, n) adj[u][v] = r();
// print_adj();
printf("%d\n", prim());
}
// fclose(stdin);
return ~~(0 ^ 0);
}
// Kruskal
signed mainII(int argc, char const* argv[]) {
// freopen("test.in", "r", stdin);
while (scanf("%d", &n) != EOF) {
edge_cnt = 0;
f(u, 0, n) f(v, 0, n) if (v > u) edges[edge_cnt++] = {int(u), int(v), int(r())}; else r();
printf("%d\n", kruskal());
}
// fclose(stdin);
return ~~(0 ^ 0);
}