===
Index
被最多点到达的节点集合
n个点，m条有向边的图，定义节点u的得分为所有不等于u且能通过某条路径到达节点u的节点数目，求节点的最大得分，以及拥有最大得分的节点集合。
- 2 <= n <= 5000
- 1 <= m <= 30000
分析
首先进行强联通分量缩点，缩点后建反向图，在该拓扑图上求每个节点能到达的节点数目即可。
void solve() {
int n, m;
cin >> n >> m;
SCC c(n);
vector<array<int, 2>> es(m);
for (int i = 0, u, v; i < m; ++i) {
cin >> u >> v;
c.add_edge(u, v);
es[i] = {u, v};
}
auto p = c.scc();
n = c.cnt;
vector<vector<int>> g(n);
vector<int> f(n);
for (int i = 0; i < n; ++i) {
f[i] = p[i].size() - 1;
}
for (auto &e : es) {
int u = c.ids[e[0]], v = c.ids[e[1]];
if (u != v) {
g[v].push_back(u);
}
}
vector<int> vis(n);
function<void(int, int)> dfs = [&](int i, int u) {
vis[u] = 1;
if (u != i) f[i] += p[u].size();
for (int v : g[u]) {
if (!vis[v]) dfs(i, v);
}
};
for (int i = 0; i < n; i++) {
if (c.in[i] == 0) continue;
vis.assign(n, 0);
dfs(i, i);
}
int mx = 0;
for (int i = 0; i < n; ++i) {
if (f[i] > mx) mx = f[i];
}
cout << mx << '\n';
vector<int> ans;
for (int i = 0; i < n; ++i) {
if (f[i] == mx) {
for (auto &x : p[i])
ans.push_back(x);
}
}
sort(ans.begin(), ans.end());
for (int i = 0, n = ans.size(); i < n; ++i) {
cout << ans[i] << " \n"[i == n - 1];
}
}
最小树形图模板
给定带权有向图G，求以节点s为根的最小树形图，该树以s为根，包含所有n个节点，树中的有向边在原图中都存在且总边权和最小。 输出总权和S，以及n个数，第i个数为第i个节点的父节点编号。
- 1 <= n <= 2e5
- n - 1 <= m <= 2e5
- 1 <= w <= 1e9
Chu-liu算法
时间复杂度 O(m*log(n))
#include <bits/stdc++.h>
using namespace std;
// https://judge.yosupo.jp/problem/directedmst
struct rollback_dsu {
explicit rollback_dsu(int n) : n(n), pa_or_siz(n, -1) {}
int get(int u) const { return pa_or_siz[u] < 0 ? u : get(pa_or_siz[u]);}
bool merge(int u, int v) {
assert(0 <= u && u < n && 0 <= v && v < n);
u = get(u), v = get(v);
if (u == v) return false;
if (-pa_or_siz[u] < -pa_or_siz[v]) std::swap(u, v);
history.emplace(v, pa_or_siz[v]);
pa_or_siz[u] += pa_or_siz[v];
pa_or_siz[v] = u;
return true;
}
int size(int u) const {
assert(0 <= u && u < n);
return -pa_or_siz[get(u)];
}
void rollback() {
assert(!history.empty());
auto [v, val] = history.top();
auto u = pa_or_siz[v];
pa_or_siz[v] = val;
pa_or_siz[u] -= val;
history.pop();
}
void rollback(int count) {
for (auto i = 0; i < count; ++i)
rollback();
}
private:
int n;
vector<int> pa_or_siz;
stack<std::pair<int, int>> history;
};
template <typename Cost> struct directed_mst {
explicit directed_mst(int _n) : n(_n), heap_(_n, -1) {}
void add_edge(int from, int to, Cost cost) {
assert(0 <= from && from < n && 0 <= to && to < n);
auto id = static_cast<int>(from_.size());
from_.push_back(from); to_.push_back(to); cost_.push_back(cost);
left_.push_back(-1); right_.push_back(-1); lazy_.push_back(Cost{});
heap_[to] = merge(heap_[to], id);
}
pair<Cost, vector<int>> get(int root, bool build_solution = false) {
rollback_dsu dsu(n);
Cost result{};
vector<int> seen(n, -1), path(n), q(n), in(n, -1);
seen[root] = root;
vector<std::pair<int, std::vector<int>>> cycles;
for (auto s = 0; s < n; ++s) {
auto u = s, pos = 0, w = -1;
while (!~seen[u]) {
if (!~heap_[u]) return {-1, {}};
push(heap_[u]);
auto e = heap_[u];
result += cost_[e];
lazy_[heap_[u]] -= cost_[e];
heap_[u] = pop(heap_[u]);
q[pos] = e;
path[pos++] = u;
seen[u] = s;
u = dsu.get(from_[e]);
if (seen[u] == s) {
auto cycle = -1;
auto end = pos;
do {
w = path[--pos];
cycle = merge(cycle, heap_[w]);
} while (dsu.merge(u, w));
u = dsu.get(u);
heap_[u] = cycle;
seen[u] = -1;
cycles.emplace_back(u,vector<int>(q.begin() + pos,q.begin() + end));
}
}
for (auto i = 0; i < pos; ++i)
in[dsu.get(to_[q[i]])] = q[i];
}
vector<int> parent;
if (build_solution) {
for (auto it = cycles.rbegin(); it != cycles.rend(); ++it) {
auto &[u, comp] = *it;
auto count = static_cast<int>(comp.size()) - 1;
dsu.rollback(count);
auto inedge = in[u];
for (auto e : comp) {
in[dsu.get(to_[e])] = e;
}
in[dsu.get(to_[inedge])] = inedge;
}
parent.reserve(n);
for (auto i : in) {
parent.push_back(~i ? from_[i] : -1);
}
}
return {result, parent};
}
private:
void push(int u) {
cost_[u] += lazy_[u];
if (~left_[u]) lazy_[left_[u]] += lazy_[u];
if (~right_[u]) lazy_[right_[u]] += lazy_[u];
lazy_[u] = 0;
}
int merge(int u, int v) {
if (!~u || !~v) return ~u ? u : v;
push(u); push(v);
if (cost_[u] > cost_[v]) swap(u, v);
right_[u] = merge(v, right_[u]);
std::swap(left_[u], right_[u]);
return u;
}
int pop(int u) {
push(u);
return merge(left_[u], right_[u]);
}
const int n;
vector<int> from_, to_, left_, right_, heap_;
vector<Cost> cost_, lazy_;
};
int main() {
cin.tie(0)->sync_with_stdio(0);
int N, M, S;
cin >> N >> M >> S;
directed_mst<long long> dmst(N);
for (auto i = 0; i < M; ++i) {
int a, b, c;
cin >> a >> b >> c;
dmst.add_edge(a, b, c);
}
auto [X, parent] = dmst.get(S, true);
parent[S] = S;
cout << X << '\n';
for (auto p : parent) {
cout << p << ' ';
}
}
虚根最小树形图
给定X,Y,Z, n个村庄，每个村庄有个三维坐标(x,y,z)，可以在每个村庄建设水井，花费 z * X，也可在村庄间建设水管，从村庄a修建到村庄b的代价为： 如果a的高度不低于b的高度，代价为 Y * Manhattan(a,b), 否则为 Z + Y * Manhattan(a,b). 另外每个村庄只能修建到部分村庄的水管，求让所有村庄都能喝上水的最少代价。
- 1 <= n <= 1000
- 1 <= x, y, z <= 1000
分析
建立一个虚拟源点，与所有点连边，边权为在该点建设水井的代价，点与点之间建边，从源点计算最小树形图即可，注意剪枝（这个模板第一次提交T了，剪掉连边大于在该处新建一个水井的边，快了很多）。
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, X, Y, Z, k, x;
while (cin >> n >> X >> Y >> Z ) {
if (!n) break;
directed_mst<long long> d(n + 1);
vector<array<int, 3>> ps(n + 1);
for (int i = 1; i <= n; ++i) {
cin >> ps[i][0] >> ps[i][1] >> ps[i][2];
}
auto dis = [&](int i, int j) {
long long d = abs(ps[i][0] - ps[j][0]) + abs(ps[i][1] - ps[j][1]) + abs(ps[i][2] - ps[j][2]);
d *= Y;
if (ps[i][2] < ps[j][2]) d += Z;
return d;
};
for (int i = 1; i <= n; ++i) {
d.add_edge(0, i, ps[i][2] * 1ll * X);
cin >> k;
for (int j = 0; j < k; ++j) {
cin >> x;
auto ds = dis(i, x);
if(i != x && ds < ps[x][2] * X) d.add_edge(i, x, ds); // 剪枝
}
}
cout << d.get(0).first << '\n';
}
return 0;
}
支配树
对于一个有向图，起点为s，对于图中的每个点w，都存在点d满足去掉d之后从s无法到达w，称作 d支配w，d是w的一个支配点。
支配w的点可以有多个，但是至少会有一个。显然，对于起点以外的点，它们都有两个平凡的支配点，一个是自己，一个是起点。
在支配w的点中，如果一个支配点i!=w 满足i被w剩下的所有非平凡支配点支配，则这个i称作w 的最近支配点(immediate dominator)，记作 idom(w)。
定理1
我们把图的起点称作s，除s以外每个点均存在唯一的idom。
支配树
连上所有s以外的idom(w) -> w的边，能得到一棵树，其中每个点支配它子树中的所有点，它就是支配树。
给定n个点，m条边的有向图，计算以s为根节点的支配树。输出n个数，第i个数为节点i的父节点编号，其中s节点输出s，如果从s无法到达节点i，输出-1.
- 1 <= n, m <= 2e5
struct dominator_tree {
explicit dominator_tree(int n)
: n(n), fa(n), idom(n, -1), sdom(n, -1), dsu(n), label(n), g(n), gr(n) {
order_.reserve(n);
iota(dsu.begin(), dsu.end(), 0);
iota(label.begin(), label.end(), 0);
}
void add_edge(int from, int to) {
assert(0 <= from && from < n && 0 <= to && to < n);
g[from].push_back(to);
gr[to].push_back(from);
}
void get(int root) {
assert(0 <= root && root < n);
dfs(root);
vector<vector<int>> bucket(n);
vector<int> x(n);
for (auto i = static_cast<int>(order_.size()) - 1; i >= 0; --i) {
auto u = order_[i];
for (auto v : gr[u]) {
if (~sdom[v]) sdom[u] = std::min(sdom[u], sdom[eval(v)]);
}
bucket[order_[sdom[u]]].push_back(u);
for (auto v : bucket[fa[u]])
x[v] = eval(v);
bucket[fa[u]].clear();
link(fa[u], u);
}
for (auto i = 1; i < static_cast<int>(order_.size()); ++i) {
auto u = order_[i], v = x[u];
idom[u] = (sdom[u] == sdom[v] ? sdom[u] : idom[v]);
}
for (auto i = 1; i < static_cast<int>(order_.size()); ++i) {
auto u = order_[i];
idom[u] = order_[idom[u]];
}
idom[root] = root;
}
int operator[](int u) const {
assert(0 <= u && u < n);
return idom[u];
}
private:
void dfs(int u) {
sdom[u] = static_cast<int>(order_.size());
order_.push_back(u);
for (auto v : g[u]) if (!~sdom[v]) {
fa[v] = u;
dfs(v);
}
}
int find(int u) {
if (dsu[u] == u) return u;
auto root = find(dsu[u]);
if (sdom[label[u]] > sdom[label[dsu[u]]]) label[u] = label[dsu[u]];
return dsu[u] = root;
}
int eval(int u) {
find(u);
return label[u];
}
void link(int u, int v) { dsu[v] = u; }
int n;
vector<int> order_, fa, idom, sdom, dsu, label;
vector<vector<int>> g, gr;
};
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
std::cin.tie(0)->sync_with_stdio(0);
int N, M, S;
std::cin >> N >> M >> S;
dominator_tree dt(N);
for (auto i = 0; i < M; ++i) {
int a, b;
std::cin >> a >> b;
dt.add_edge(a, b);
}
dt.get(S);
for (auto i = 0; i < N; ++i) {
std::cout << dt[i] << ' ';
}
return 0;
}
曼哈顿生成树
给定二维平面上n个点，任意两个点增加一条长为曼哈顿距离的无向边，求图中的最小生成树。
- 1 <= n <= 2e5
- 0 <= x, y <= 1e9
struct DSU {
vector<int> p, siz;
DSU(int n) : p(n), siz(n, 1) { iota(p.begin(), p.end(), 0); }
inline int get(int x) { return (x == p[x] ? x : (p[x] = get(p[x])));}
bool same(int x, int y) { return get(x) == get(y); }
bool merge(int x, int y) {
x = get(x), y = get(y);
if (x == y) return false;
siz[x] += siz[y];
p[y] = x;
return true;
}
int size(int x) { return siz[get(x)]; }
vector<vector<int>> groups() {
vector<vector<int>> res(p.size());
for (int i = 0; i < p.size(); i++) res[get(i)].push_back(i);
res.erase(
remove_if(res.begin(), res.end(),
[&](const vector<int>& v) { return v.empty(); }),
res.end());
return res;
}
};
template <typename T, typename Comp>
struct KruscalMST {
KruscalMST() : KruscalMST(0) {}
explicit KruscalMST(const int n) : _n(n) {}
void add_edge(const int u, const int v, const T& cost) { _built = false; es.emplace_back(u, v, cost);}
void add_edge(const tuple<int, int, T>& e) { _built = false; es.push_back(e);}
bool build() {
_built = true, _weight_sum = 0;
if (_n == 0) return true;
DSU uf(_n);
sort(es.begin(), es.end(), [this](const auto& u, const auto& v) { return _comp(std::get<2>(u), std::get<2>(v));});
for (auto& [u, v, w] : es) {
if (uf.same(u, v)) u = v = _n;
else { uf.merge(u, v); _weight_sum += w;}
}
es.erase(std::remove_if(es.begin(), es.end(), [this](auto& e) { return std::get<0>(e) == _n; }), es.end());
return int(es.size()) == _n - 1;
}
T get_weight() const { assert(_built); return _weight_sum;}
const std::vector<tuple<int, int, T>>& get_mst() const { assert(_built); return es;}
private:
int _n;
T _weight_sum;
Comp _comp{};
vector<tuple<int, int, T>> es;
bool _built = false;
};
template <typename T> using minMst = KruscalMST<T, less<T>>;
template <typename T> using maxMst = KruscalMST<T, greater<T>>;
template <typename WeightType, typename T>
minMst<WeightType> manhattan_mst(vector<pair<T, T>> points) {
const int n = points.size();
vector<int> p(n);
iota(p.begin(), p.end(), 0);
auto makees = [&](minMst<WeightType> &mst) {
std::sort(
p.begin(), p.end(),
[&points](int i, int j) {
const auto &[xi, yi] = points[i];
const auto &[xj, yj] = points[j];
return yi - xi == yj - xj ? xi < xj : yi - xi < yj - xj;
}
);
vector<T> comp_x(n);
for (int i = 0; i < n; ++i) comp_x[i] = points[i].first;
sort(comp_x.begin(), comp_x.end());
comp_x.erase(unique(comp_x.begin(), comp_x.end()), comp_x.end());
const int m = comp_x.size();
auto get = [&](const T& x) { return lower_bound(comp_x.begin(), comp_x.end(), x) - comp_x.begin();};
struct PrefixMaxQuery {
const std::pair<T, int> _neg_inf{ std::numeric_limits<T>::min(), -1 };
int _n;
std::vector<std::pair<T, int>> _dat;
PrefixMaxQuery(int n) : _n(n), _dat(_n + 1, _neg_inf) {}
void chmax(int i, const std::pair<T, int>& val) {
for (++i; i <= _n; i += -i & i) if (_dat[i].first < val.first) _dat[i] = val;
}
std::pair<T, int> prefix_max(int r) const {
std::pair<T, int> res = _neg_inf;
for (; r; r -= -r & r) if (res.first < _dat[r].first) res = _dat[r];
return res;
}
} pmq{ m };
for (int i : p) {
const auto& [x, y] = points[i];
const int cx = get(x);
if (const auto p = pmq.prefix_max(cx + 1); p != pmq._neg_inf) {
const auto& [v, j] = p;
mst.add_edge(i, j, x + y - v);
}
pmq.chmax(cx, { x + y, i });
}
};
minMst<WeightType> mst(n);
for (int x_rev = 0; x_rev < 2; ++x_rev) {
for (int y_rev = 0; y_rev < 2; ++y_rev) {
for (int xy_rev = 0; xy_rev < 2; ++xy_rev) {
makees(mst);
for (auto& [x, y] : points) std::swap(x, y);
}
for (auto& [x, _] : points) x = -x;
}
for (auto& [_, y] : points) y = -y;
}
assert(mst.build());
return mst;
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int n;
std::cin >> n;
std::vector<std::pair<int, int>> points(n);
for (auto &[x, y] : points) std::cin >> x >> y;
auto mst = manhattan_mst<long long>(points);
std::cout << mst.get_weight() << '\n';
for (auto [i, j, _] : mst.get_mst()) {
std::cout << i << ' ' << j << '\n';
}
return 0;
}
