maximum_weight_closure.hpp¶
求有向依赖图的最大权闭包；先缩强连通分量，再把分量收益选择转成最小割。返回包含关系下最小的最优方案，正权总和须不超过 INT64_MAX。
Complexity: Time: \(O(n + m)\) condensation, then \(O(k^{2} (k + e))\) Dinic, where \(k\) is the SCC count and \(e\) counts dependencies between SCCs. Space: \(O(n + m)\), including \(O(n)\) recursive SCC/flow depth.
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(n + m) condensation, then O(k^2 (k + e)) Dinic,
/// where k is the SCC count and e counts dependencies between SCCs.
/// Space: O(n + m), including O(n) recursive SCC/flow depth.
#include "atcoder/maxflow.hpp"
#include "atcoder/internal_scc.hpp"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <limits>
#include <utility>
#include <vector>
namespace noya {
struct maximum_weight_closure_result {
std::int64_t w = 0;
std::vector<int> sel;
};
/// @brief Maximum-weight vertex set closed under dependencies u -> v.
/// Positive weights must sum to at most INT64_MAX; INT64_MIN is allowed.
/// Return the inclusion-minimal optimum, with selected vertices in index order.
/// Loops/duplicate dependencies are harmless; input is not modified.
inline maximum_weight_closure_result
maximum_weight_closure(const std::vector<std::int64_t> &w,
const std::vector<std::pair<int, int>> &dep) {
assert(w.size() <= std::size_t(std::numeric_limits<int>::max() - 2));
int n = int(w.size()), positives = 0;
assert(dep.size() <= std::size_t(std::numeric_limits<int>::max() - n));
for ([[maybe_unused]] auto [u, v] : dep)
assert(0 <= u && u < n && 0 <= v && v < n);
__int128 sum = 0;
for (auto value : w) if (value > 0) {
sum += value;
++positives;
}
assert(sum <= std::numeric_limits<std::int64_t>::max());
maximum_weight_closure_result res;
if (!positives) return res;
if (dep.empty() || positives == n) {
res.w = std::int64_t(sum);
res.sel.reserve(positives);
for (int u = 0; u < n; ++u) if (w[u] > 0) res.sel.push_back(u);
return res;
}
// A closure contains either every vertex of an SCC or none of them.
// Only IDs are needed; avoid allocating a vertex vector for each component.
auto [k, id] = [&] {
atcoder::internal::scc_graph graph(n);
for (auto [u, v] : dep) if (u != v) graph.add_edge(u, v);
return graph.scc_ids();
}();
std::vector<__int128> weight(k);
for (int u = 0; u < n; ++u) weight[id[u]] += w[u];
using cap = std::uint64_t;
cap positive = 0;
for (auto value : weight) if (value > 0) positive += cap(value);
if (!positive) return res;
cap inf = positive + 1;
atcoder::mf_graph<cap> flow(k + 2);
for (int c = 0; c < k; ++c) {
if (weight[c] > 0) flow.add_edge(k, c, cap(weight[c]));
// The empty closure gives a cut of capacity positive, so larger negative
// penalties can be capped at inf without changing any minimum cut.
else if (weight[c] < 0)
flow.add_edge(c, k + 1, cap(std::min<__int128>(-weight[c], inf)));
}
for (auto [u, v] : dep)
if (id[u] != id[v]) flow.add_edge(id[u], id[v], inf);
res.w = std::int64_t(positive - flow.flow(k, k + 1, positive));
auto selected = flow.min_cut(k);
res.sel.reserve(n);
for (int u = 0; u < n; ++u) if (selected[id[u]]) res.sel.push_back(u);
return res;
}
} // namespace noya
// NOYA_MAXIMUM_WEIGHT_CLOSURE_HPP
#ifndef NOYA_MAXIMUM_WEIGHT_CLOSURE_HPP
#define NOYA_MAXIMUM_WEIGHT_CLOSURE_HPP 1
/// @complexity Time: O(n + m) condensation, then O(k^2 (k + e)) Dinic,
/// where k is the SCC count and e counts dependencies between SCCs.
/// Space: O(n + m), including O(n) recursive SCC/flow depth.
#include "atcoder/maxflow.hpp"
#include "atcoder/internal_scc.hpp"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <limits>
#include <utility>
#include <vector>
namespace noya {
struct maximum_weight_closure_result {
std::int64_t w = 0;
std::vector<int> sel;
};
/// @brief Maximum-weight vertex set closed under dependencies u -> v.
/// Positive weights must sum to at most INT64_MAX; INT64_MIN is allowed.
/// Return the inclusion-minimal optimum, with selected vertices in index order.
/// Loops/duplicate dependencies are harmless; input is not modified.
inline maximum_weight_closure_result
maximum_weight_closure(const std::vector<std::int64_t> &w,
const std::vector<std::pair<int, int>> &dep) {
assert(w.size() <= std::size_t(std::numeric_limits<int>::max() - 2));
int n = int(w.size()), positives = 0;
assert(dep.size() <= std::size_t(std::numeric_limits<int>::max() - n));
for ([[maybe_unused]] auto [u, v] : dep)
assert(0 <= u && u < n && 0 <= v && v < n);
__int128 sum = 0;
for (auto value : w) if (value > 0) {
sum += value;
++positives;
}
assert(sum <= std::numeric_limits<std::int64_t>::max());
maximum_weight_closure_result res;
if (!positives) return res;
if (dep.empty() || positives == n) {
res.w = std::int64_t(sum);
res.sel.reserve(positives);
for (int u = 0; u < n; ++u) if (w[u] > 0) res.sel.push_back(u);
return res;
}
// A closure contains either every vertex of an SCC or none of them.
// Only IDs are needed; avoid allocating a vertex vector for each component.
auto [k, id] = [&] {
atcoder::internal::scc_graph graph(n);
for (auto [u, v] : dep) if (u != v) graph.add_edge(u, v);
return graph.scc_ids();
}();
std::vector<__int128> weight(k);
for (int u = 0; u < n; ++u) weight[id[u]] += w[u];
using cap = std::uint64_t;
cap positive = 0;
for (auto value : weight) if (value > 0) positive += cap(value);
if (!positive) return res;
cap inf = positive + 1;
atcoder::mf_graph<cap> flow(k + 2);
for (int c = 0; c < k; ++c) {
if (weight[c] > 0) flow.add_edge(k, c, cap(weight[c]));
// The empty closure gives a cut of capacity positive, so larger negative
// penalties can be capped at inf without changing any minimum cut.
else if (weight[c] < 0)
flow.add_edge(c, k + 1, cap(std::min<__int128>(-weight[c], inf)));
}
for (auto [u, v] : dep)
if (id[u] != id[v]) flow.add_edge(id[u], id[v], inf);
res.w = std::int64_t(positive - flow.flow(k, k + 1, positive));
auto selected = flow.min_cut(k);
res.sel.reserve(n);
for (int u = 0; u < n; ++u) if (selected[id[u]]) res.sel.push_back(u);
return res;
}
} // namespace noya
#endif // NOYA_MAXIMUM_WEIGHT_CLOSURE_HPP
/// @complexity Time: O(n + m) condensation, then O(k^2 (k + e)) Dinic,
/// where k is the SCC count and e counts dependencies between SCCs.
/// Space: O(n + m), including O(n) recursive SCC/flow depth.
#include <algorithm>
#include <cassert>
#include <limits>
#include <queue>
#include <vector>
#include <vector>
namespace atcoder {
namespace internal {
template <class T> struct simple_queue {
std::vector<T> payload;
int pos = 0;
void reserve(int n) { payload.reserve(n); }
int size() const { return int(payload.size()) - pos; }
bool empty() const { return pos == int(payload.size()); }
void push(const T& t) { payload.push_back(t); }
T& front() { return payload[pos]; }
void clear() {
payload.clear();
pos = 0;
}
void pop() { pos++; }
};
} // namespace internal
} // namespace atcoder
namespace atcoder {
template <class Cap> struct mf_graph {
public:
mf_graph() : _n(0) {}
explicit mf_graph(int n) : _n(n), g(n) {}
int add_edge(int from, int to, Cap cap) {
assert(0 <= from && from < _n);
assert(0 <= to && to < _n);
assert(0 <= cap);
int m = int(pos.size());
pos.push_back({from, int(g[from].size())});
int from_id = int(g[from].size());
int to_id = int(g[to].size());
if (from == to) to_id++;
g[from].push_back(_edge{to, to_id, cap});
g[to].push_back(_edge{from, from_id, 0});
return m;
}
struct edge {
int from, to;
Cap cap, flow;
};
edge get_edge(int i) {
int m = int(pos.size());
assert(0 <= i && i < m);
auto _e = g[pos[i].first][pos[i].second];
auto _re = g[_e.to][_e.rev];
return edge{pos[i].first, _e.to, _e.cap + _re.cap, _re.cap};
}
std::vector<edge> edges() {
int m = int(pos.size());
std::vector<edge> result;
for (int i = 0; i < m; i++) {
result.push_back(get_edge(i));
}
return result;
}
void change_edge(int i, Cap new_cap, Cap new_flow) {
int m = int(pos.size());
assert(0 <= i && i < m);
assert(0 <= new_flow && new_flow <= new_cap);
auto& _e = g[pos[i].first][pos[i].second];
auto& _re = g[_e.to][_e.rev];
_e.cap = new_cap - new_flow;
_re.cap = new_flow;
}
Cap flow(int s, int t) {
return flow(s, t, std::numeric_limits<Cap>::max());
}
Cap flow(int s, int t, Cap flow_limit) {
assert(0 <= s && s < _n);
assert(0 <= t && t < _n);
assert(s != t);
std::vector<int> level(_n), iter(_n);
internal::simple_queue<int> que;
auto bfs = [&]() {
std::fill(level.begin(), level.end(), -1);
level[s] = 0;
que.clear();
que.push(s);
while (!que.empty()) {
int v = que.front();
que.pop();
for (auto e : g[v]) {
if (e.cap == 0 || level[e.to] >= 0) continue;
level[e.to] = level[v] + 1;
if (e.to == t) return;
que.push(e.to);
}
}
};
auto dfs = [&](auto self, int v, Cap up) {
if (v == s) return up;
Cap res = 0;
int level_v = level[v];
for (int& i = iter[v]; i < int(g[v].size()); i++) {
_edge& e = g[v][i];
if (level_v <= level[e.to] || g[e.to][e.rev].cap == 0) continue;
Cap d =
self(self, e.to, std::min(up - res, g[e.to][e.rev].cap));
if (d <= 0) continue;
g[v][i].cap += d;
g[e.to][e.rev].cap -= d;
res += d;
if (res == up) return res;
}
level[v] = _n;
return res;
};
Cap flow = 0;
while (flow < flow_limit) {
bfs();
if (level[t] == -1) break;
std::fill(iter.begin(), iter.end(), 0);
Cap f = dfs(dfs, t, flow_limit - flow);
if (!f) break;
flow += f;
}
return flow;
}
std::vector<bool> min_cut(int s) {
std::vector<bool> visited(_n);
internal::simple_queue<int> que;
que.push(s);
while (!que.empty()) {
int p = que.front();
que.pop();
visited[p] = true;
for (auto e : g[p]) {
if (e.cap && !visited[e.to]) {
visited[e.to] = true;
que.push(e.to);
}
}
}
return visited;
}
private:
int _n;
struct _edge {
int to, rev;
Cap cap;
};
std::vector<std::pair<int, int>> pos;
std::vector<std::vector<_edge>> g;
};
} // namespace atcoder
#include <algorithm>
#include <utility>
#include <vector>
#include <algorithm>
#include <utility>
#include <vector>
namespace atcoder {
namespace internal {
template <class E> struct csr {
std::vector<int> start;
std::vector<E> elist;
explicit csr(int n, const std::vector<std::pair<int, E>>& edges)
: start(n + 1), elist(edges.size()) {
for (auto e : edges) {
start[e.first + 1]++;
}
for (int i = 1; i <= n; i++) {
start[i] += start[i - 1];
}
auto counter = start;
for (auto e : edges) {
elist[counter[e.first]++] = e.second;
}
}
};
} // namespace internal
} // namespace atcoder
namespace atcoder {
namespace internal {
// Reference:
// R. Tarjan,
// Depth-First Search and Linear Graph Algorithms
struct scc_graph {
public:
explicit scc_graph(int n) : _n(n) {}
int num_vertices() { return _n; }
void add_edge(int from, int to) { edges.push_back({from, {to}}); }
// @return pair of (# of scc, scc id)
std::pair<int, std::vector<int>> scc_ids() {
auto g = csr<edge>(_n, edges);
int now_ord = 0, group_num = 0;
std::vector<int> visited, low(_n), ord(_n, -1), ids(_n);
visited.reserve(_n);
auto dfs = [&](auto self, int v) -> void {
low[v] = ord[v] = now_ord++;
visited.push_back(v);
for (int i = g.start[v]; i < g.start[v + 1]; i++) {
auto to = g.elist[i].to;
if (ord[to] == -1) {
self(self, to);
low[v] = std::min(low[v], low[to]);
} else {
low[v] = std::min(low[v], ord[to]);
}
}
if (low[v] == ord[v]) {
while (true) {
int u = visited.back();
visited.pop_back();
ord[u] = _n;
ids[u] = group_num;
if (u == v) break;
}
group_num++;
}
};
for (int i = 0; i < _n; i++) {
if (ord[i] == -1) dfs(dfs, i);
}
for (auto& x : ids) {
x = group_num - 1 - x;
}
return {group_num, ids};
}
std::vector<std::vector<int>> scc() {
auto ids = scc_ids();
int group_num = ids.first;
std::vector<int> counts(group_num);
for (auto x : ids.second) counts[x]++;
std::vector<std::vector<int>> groups(ids.first);
for (int i = 0; i < group_num; i++) {
groups[i].reserve(counts[i]);
}
for (int i = 0; i < _n; i++) {
groups[ids.second[i]].push_back(i);
}
return groups;
}
private:
int _n;
struct edge {
int to;
};
std::vector<std::pair<int, edge>> edges;
};
} // namespace internal
} // namespace atcoder
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <limits>
#include <utility>
#include <vector>
namespace noya {
struct maximum_weight_closure_result {
std::int64_t w = 0;
std::vector<int> sel;
};
/// @brief Maximum-weight vertex set closed under dependencies u -> v.
/// Positive weights must sum to at most INT64_MAX; INT64_MIN is allowed.
/// Return the inclusion-minimal optimum, with selected vertices in index order.
/// Loops/duplicate dependencies are harmless; input is not modified.
inline maximum_weight_closure_result
maximum_weight_closure(const std::vector<std::int64_t> &w,
const std::vector<std::pair<int, int>> &dep) {
assert(w.size() <= std::size_t(std::numeric_limits<int>::max() - 2));
int n = int(w.size()), positives = 0;
assert(dep.size() <= std::size_t(std::numeric_limits<int>::max() - n));
for ([[maybe_unused]] auto [u, v] : dep)
assert(0 <= u && u < n && 0 <= v && v < n);
__int128 sum = 0;
for (auto value : w) if (value > 0) {
sum += value;
++positives;
}
assert(sum <= std::numeric_limits<std::int64_t>::max());
maximum_weight_closure_result res;
if (!positives) return res;
if (dep.empty() || positives == n) {
res.w = std::int64_t(sum);
res.sel.reserve(positives);
for (int u = 0; u < n; ++u) if (w[u] > 0) res.sel.push_back(u);
return res;
}
// A closure contains either every vertex of an SCC or none of them.
// Only IDs are needed; avoid allocating a vertex vector for each component.
auto [k, id] = [&] {
atcoder::internal::scc_graph graph(n);
for (auto [u, v] : dep) if (u != v) graph.add_edge(u, v);
return graph.scc_ids();
}();
std::vector<__int128> weight(k);
for (int u = 0; u < n; ++u) weight[id[u]] += w[u];
using cap = std::uint64_t;
cap positive = 0;
for (auto value : weight) if (value > 0) positive += cap(value);
if (!positive) return res;
cap inf = positive + 1;
atcoder::mf_graph<cap> flow(k + 2);
for (int c = 0; c < k; ++c) {
if (weight[c] > 0) flow.add_edge(k, c, cap(weight[c]));
// The empty closure gives a cut of capacity positive, so larger negative
// penalties can be capped at inf without changing any minimum cut.
else if (weight[c] < 0)
flow.add_edge(c, k + 1, cap(std::min<__int128>(-weight[c], inf)));
}
for (auto [u, v] : dep)
if (id[u] != id[v]) flow.add_edge(id[u], id[v], inf);
res.w = std::int64_t(positive - flow.flow(k, k + 1, positive));
auto selected = flow.min_cut(k);
res.sel.reserve(n);
for (int u = 0; u < n; ++u) if (selected[id[u]]) res.sel.push_back(u);
return res;
}
} // namespace noya
// NOYA_MAXIMUM_WEIGHT_CLOSURE_HPP