最小生成树模板
- Kruskal – 基于并查集
- Prim – 基于贪心
Kruskal
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
#include <bits/stdc++.h> using namespace std; typedef long long LL; const LL maxn = 100 + 1; LL father[maxn]; LL n, m; struct edge { LL from, to, cost; edge(LL from_ = 0, LL to_ = 0, LL cost_ = 0): from(from_), to(to_), cost(cost_) {} friend inline bool operator < (const edge &e_1, const edge &e_2) { return e_1.cost < e_2.cost; } } E[maxn * maxn]; void init() { for (LL i = 1; i <= n; ++i) father[i] = i; } LL find(LL u) { return father[u] == u ? father[u] : father[u] = find(father[u]); } void join(LL u, LL v) { father[find(v)] = find(u); } LL Kruskal() { sort(E + 1, E + m + 1); init(); LL ret = 0; for (LL i = 1; i <= m; ++i) { if (find(E[i].from) != find(E[i].to)) { ret += E[i].cost; join(E[i].from, E[i].to); } } return ret; } int main() { ios::sync_with_stdio(false); LL ans, is_connect; while (cin >> m >> n && m != 0) { for (LL i = 1; i <= m; ++i) cin >> E[i].from >> E[i].to >> E[i].cost; ans = Kruskal(); is_connect = true; for (LL i = 1; i <= n; ++i) { if (find(1) != find(i)) is_connect = false; } if (!is_connect) cout << "?" << endl; else cout << ans << endl; } return 0; } |
Prim
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 |
#include <bits/stdc++.h> using namespace std; typedef long long LL; const LL maxn = 100 + 1; struct edge { LL to, cost; edge(LL to_ = 0, LL cost_ = 0): to(to_), cost(cost_) {} friend bool operator > (const edge &e_1, const edge &e_2) { return e_1.cost > e_2.cost; } }; LL n, m; vector <edge> g[maxn]; priority_queue <edge, vector<edge>, greater<edge> > q; bool vis[maxn]; LL Prim() { memset(vis, 0, sizeof vis); LL ret = 0; vis[1] = 1; for (unsigned i = 0; i < g[1].size(); ++i) { q.push(g[1][i]); } edge e; while (!q.empty()) { e = q.top(); q.pop(); if (!vis[e.to]) { vis[e.to] = 1; ret += e.cost; for (unsigned i = 0; i < g[e.to].size(); ++i) { q.push(g[e.to][i]); } } } return ret; } int main() { ios::sync_with_stdio(false); LL tu, tv, tc, ans; while (cin >> m >> n && m != 0) { for (LL i = 1; i <= n; ++i) g[i].clear(); while (!q.empty()) { q.pop(); } for (LL i = 1; i <= m; ++i) { cin >> tu >> tv >> tc; g[tu].push_back(edge(tv, tc)); g[tv].push_back(edge(tu, tc)); } ans = Prim(); for (LL i = 1; i <= n; ++i) { if (!vis[i]) { ans = -1; } } if (ans == -1) cout << "?" << endl; else cout << ans << endl; } return 0; } |
说点什么