This documentation is automatically generated by competitive-verifier/competitive-verifier
#include "graph/others/extreme-vertex-set.hpp"
重み付き無向グラフ $G$ が与えられたとき、$G$ の Extreme Vertex Set(極点集合)をすべて列挙します。
template<typename T>
Graph<T> extreme_vertex_set(int n, const Edges<T> &es)
頂点数 $n$、辺が es
からなる $G$ の Extreme Vertex Set を返します。
$2n - 1$ 頂点の根付きで表されます。根は $2n - 2$ です。頂点 $[0, n)$ は葉で、もとのグラフの頂点に対応します。それぞれの部分木が Extreme Vertex Set の候補に対応し、部分木からその親に生える辺の重みが、カットのコストです。
#include "../graph-template.hpp"
template <typename T>
Graph<T> extreme_vertex_set(int n, const Edges<T> &es) {
for (auto &e : es) {
assert(0 <= e.from and e.from < n);
assert(0 <= e.to and e.to < n);
assert(e.from != e.to);
assert(0 <= e.cost);
}
using pi = pair<int, T>;
Graph<T> res(2 * n - 1);
vector<int> uf(n);
vector<T> cur(2 * n - 1);
iota(uf.begin(), uf.end(), 0);
vector<bool> leaf(2 * n - 1);
for (int i = 0; i < n; i++) {
leaf[i] = true;
}
using qi = pair<T, int>;
priority_queue<qi, vector<qi>, greater<> > que;
for (int phase = 0; phase < n - 1; phase++) {
Graph<T> g(2 * n - 1);
vector<T> cost(2 * n - 1);
for (auto e : es) {
e.from = uf[e.from];
e.to = uf[e.to];
if (e.from != e.to) {
cost[e.from] += e.cost;
cost[e.to] += e.cost;
g.add_edge(e.from, e.to, e.cost);
}
}
for (int i = 0; i < 2 * n - 1; i++) {
if (leaf[i]) {
cur[i] = cost[i];
que.emplace(cost[i], i);
}
}
int x = -1, y = -1;
while (not que.empty()) {
auto [c, v] = que.top();
que.pop();
if (cur[v] == -1) {
continue;
}
cur[v] = -1;
y = x;
x = v;
for (auto &e : g[v]) {
if (cur[e.to] != -1) {
cur[e.to] -= e.cost;
que.emplace(cur[e.to], e.to);
}
}
}
int z = n + phase;
res.add_directed_edge(z, x, cost[x]);
res.add_directed_edge(z, y, cost[y]);
for (int i = 0; i < n; i++) {
if (uf[i] == x or uf[i] == y) {
uf[i] = z;
}
}
leaf[x] = false;
leaf[y] = false;
leaf[z] = true;
}
return res;
}
#line 2 "graph/graph-template.hpp"
template <typename T = int>
struct Edge {
int from, to;
T cost;
int idx;
Edge() = default;
Edge(int from, int to, T cost = 1, int idx = -1)
: from(from), to(to), cost(cost), idx(idx) {}
operator int() const { return to; }
};
template <typename T = int>
struct Graph {
vector<vector<Edge<T> > > g;
int es;
Graph() = default;
explicit Graph(int n) : g(n), es(0) {}
size_t size() const { return g.size(); }
void add_directed_edge(int from, int to, T cost = 1) {
g[from].emplace_back(from, to, cost, es++);
}
void add_edge(int from, int to, T cost = 1) {
g[from].emplace_back(from, to, cost, es);
g[to].emplace_back(to, from, cost, es++);
}
void read(int M, int padding = -1, bool weighted = false,
bool directed = false) {
for (int i = 0; i < M; i++) {
int a, b;
cin >> a >> b;
a += padding;
b += padding;
T c = T(1);
if (weighted) cin >> c;
if (directed)
add_directed_edge(a, b, c);
else
add_edge(a, b, c);
}
}
inline vector<Edge<T> > &operator[](const int &k) { return g[k]; }
inline const vector<Edge<T> > &operator[](const int &k) const { return g[k]; }
};
template <typename T = int>
using Edges = vector<Edge<T> >;
#line 2 "graph/others/extreme-vertex-set.hpp"
template <typename T>
Graph<T> extreme_vertex_set(int n, const Edges<T> &es) {
for (auto &e : es) {
assert(0 <= e.from and e.from < n);
assert(0 <= e.to and e.to < n);
assert(e.from != e.to);
assert(0 <= e.cost);
}
using pi = pair<int, T>;
Graph<T> res(2 * n - 1);
vector<int> uf(n);
vector<T> cur(2 * n - 1);
iota(uf.begin(), uf.end(), 0);
vector<bool> leaf(2 * n - 1);
for (int i = 0; i < n; i++) {
leaf[i] = true;
}
using qi = pair<T, int>;
priority_queue<qi, vector<qi>, greater<> > que;
for (int phase = 0; phase < n - 1; phase++) {
Graph<T> g(2 * n - 1);
vector<T> cost(2 * n - 1);
for (auto e : es) {
e.from = uf[e.from];
e.to = uf[e.to];
if (e.from != e.to) {
cost[e.from] += e.cost;
cost[e.to] += e.cost;
g.add_edge(e.from, e.to, e.cost);
}
}
for (int i = 0; i < 2 * n - 1; i++) {
if (leaf[i]) {
cur[i] = cost[i];
que.emplace(cost[i], i);
}
}
int x = -1, y = -1;
while (not que.empty()) {
auto [c, v] = que.top();
que.pop();
if (cur[v] == -1) {
continue;
}
cur[v] = -1;
y = x;
x = v;
for (auto &e : g[v]) {
if (cur[e.to] != -1) {
cur[e.to] -= e.cost;
que.emplace(cur[e.to], e.to);
}
}
}
int z = n + phase;
res.add_directed_edge(z, x, cost[x]);
res.add_directed_edge(z, y, cost[y]);
for (int i = 0; i < n; i++) {
if (uf[i] == x or uf[i] == y) {
uf[i] = z;
}
}
leaf[x] = false;
leaf[y] = false;
leaf[z] = true;
}
return res;
}