最小生成树
Graph
template <typename T>
class graph {
public:
struct edge {
int from;
int to;
T cost;
};
const int n;
std::vector<edge> edges;
std::vector<std::vector<int>> g;
graph(int _n) : n(_n), g(_n) {}
virtual int add(int from, int to, T cost) = 0;
};
template <typename T>
class digraph : public graph<T> {
public:
using graph<T>::edges;
using graph<T>::g;
using graph<T>::n;
digraph(int _n) : graph<T>(_n) {}
int add(int from, int to, T cost = 1) {
assert(0 <= from && from < n && 0 <= to && to < n);
int id = (int) edges.size();
g[from].push_back(id);
edges.push_back({from, to, cost});
return id;
}
digraph<T> reverse() const {
digraph<T> rev(n);
for (auto &e : edges) {
rev.add(e.to, e.from, e.cost);
}
return rev;
}
};
template <typename T>
class undigraph : public graph<T> {
public:
using graph<T>::edges;
using graph<T>::g;
using graph<T>::n;
undigraph(int _n) : graph<T>(_n) {}
int add(int from, int to, T cost = 1) {
assert(0 <= from && from < n && 0 <= to && to < n);
int id = (int) edges.size();
g[from].push_back(id);
g[to].push_back(id);
edges.push_back({from, to, cost});
return id;
}
};
- kruskal
struct DSU {
std::vector<int> f, siz;
int components = 0;
DSU(int n) : f(n), siz(n, 1), components(n) {
std::iota(f.begin(), f.end(), 0);
}
inline int find(int x) {
while(x != f[x]) {
x = f[x] = f[f[x]];
}
return x;
}
bool same(int x, int y) {
return find(x) == find(y);
}
bool merge(int x, int y) {
x = find(x);
y = find(y);
if(x == y) {
return false;
}
siz[x] += siz[y];
f[y] = x;
components--;
return true;
}
int size(int x) {
return siz[find(x)];
}
int total_components() {
return components;
}
};
template <typename T>
std::vector<int> kruskal(const undigraph<T> &g, T& ans) {
std::vector<int> order(g.edges.size());
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&g](int a, int b) {
return g.edges[a].cost < g.edges[b].cost;
});
DSU d(g.n);
std::vector<int> ans_list;
ans = 0;
for (int id : order) {
auto &e = g.edges[id];
if (!d.same(e.from, e.to)) {
d.merge(e.from, e.to);
ans_list.push_back(id);
ans += e.cost;
}
}
return ans_list;
// returns edge ids of minimum "spanning" forest
}
- prim
template <typename T>
bool prim(const undigraph<T> &g, T& ans) {
std::vector<bool> vis(g.n);
std::priority_queue<std::pair<T, int>, std::vector<std::pair<T, int>>, std::greater<std::pair<T, int>> > q;
q.push({0, 0});
int cnt = 0; ans = 0;
while (!q.empty() && cnt < g.n) {
T expected = q.top().first;
int u = q.top().second; q.pop();
if (vis[u]) continue;
vis[u] = true;
ans += expected; cnt++;
for (int id : g.g[u]) {
auto &e = g.edges[id];
int to = e.from ^ e.to ^ u;
if (!vis[to]) {
q.push({e.cost, to});
}
}
}
return cnt == g.n;
// returns false if there's not connected
}
最后更新:
2024年1月2日 21:37:12
创建日期: 2024年1月2日 19:47:42
创建日期: 2024年1月2日 19:47:42