AOJ 2293: Dangerous Tower
solution
負辺ありの最小費用流に帰着。速い$O(N^3)$。
考えるべき制約は$3$つ。
- 値が$X$なものは高々ひとつまでしか使えない
- 各$i$について$A_i$と$B_i$のそれぞれに使えば得られる得点があり、これを最大化したい
- 各$i$について$A_i$か$B_i$のどちらか一方までしか使えない
これを最小費用流として表現する。 始点$\mathrm{src}$ 終点$\mathrm{dst}$ 各値$X$ごとに頂点$X$ 各$i$ごとに頂点$i$を用意して、それぞれ:
- 容量$1$の辺$\mathrm{src} \to X$を各値$X$について(一度ずつだけ)張る
- 値$A_i, \; B_i$からそれぞれ頂点$i$に対し、費用$- B_i, \; - A_i$の辺を張る
- 容量$1$の辺$i \to \mathrm{dst}$を各$i$について張る
これは$3$つの制約を上手く表現できており、最小費用流を流せば解ける。 ただし流量は固定でないので、容量$\infty$費用$0$の辺$\mathrm{src} \to \mathrm{dst}$を張った上で十分多くの量を流させればよい。
implementation
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <tuple>
#include <cassert>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using namespace std;
template <class T> inline void setmin(T & a, T const & b) { a = min(a, b); }
template <class T> using reversed_priority_queue = priority_queue<T, vector<T>, greater<T> >;
template <class T>
struct edge_t { int to; T cap, cost; int rev; };
template <class T>
void add_edge(vector<vector<edge_t<T> > > & graph, int from, int to, T cap, T cost) {
graph[from].push_back((edge_t<T>) { to, cap, cost, int(graph[ to].size()) });
graph[ to].push_back((edge_t<T>) { from, 0, - cost, int(graph[from].size()) - 1 });
}
/**
* @brief minimum-cost flow with primal-dual method
* @note mainly O(V^2UC) for U is the sum of capacities and C is the sum of costs. and additional O(VE) if negative edges exist
*/
template <class T>
T min_cost_flow_destructive(int src, int dst, T flow, vector<vector<edge_t<T> > > & graph) {
T result = 0;
vector<T> potential(graph.size());
if (0 < flow) { // initialize potential when negative edges exist (slow). you can remove this if unnecessary
whole(fill, potential, numeric_limits<T>::max());
potential[src] = 0;
while (true) { // Bellman-Ford algorithm
bool updated = false;
repeat (e_from, graph.size()) for (auto & e : graph[e_from]) if (e.cap) {
if (potential[e_from] == numeric_limits<T>::max()) continue;
if (potential[e.to] > potential[e_from] + e.cost) {
potential[e.to] = potential[e_from] + e.cost; // min
updated = true;
}
}
if (not updated) break;
// TODO: detect negative loops
}
}
while (0 < flow) {
// update potential using dijkstra
vector<T> distance(graph.size(), numeric_limits<T>::max()); // minimum distance
vector<int> prev_v(graph.size()); // constitute a single-linked-list represents the flow-path
vector<int> prev_e(graph.size());
{ // initialize distance and prev_{v,e}
reversed_priority_queue<pair<T, int> > q; // distance * vertex
distance[src] = 0;
q.emplace(0, src);
while (not q.empty()) { // Dijkstra's algorithm
T d; int v; tie(d, v) = q.top(); q.pop();
if (distance[v] < d) continue;
// look round the vertex
repeat (e_index, graph[v].size()) {
// consider updating
edge_t<T> e = graph[v][e_index];
int w = e.to;
T d1 = distance[v] + e.cost + potential[v] - potential[w]; // updated distance
if (0 < e.cap and d1 < distance[e.to]) {
distance[w] = d1;
prev_v[w] = v;
prev_e[w] = e_index;
q.emplace(d1, w);
}
}
}
}
if (distance[dst] == numeric_limits<T>::max()) return -1; // no such flow
repeat (v, graph.size()) potential[v] += distance[v];
// finish updating the potential
// let flow on the src->dst minimum path
T delta = flow; // capacity of the path
for (int v = dst; v != src; v = prev_v[v]) {
setmin(delta, graph[prev_v[v]][prev_e[v]].cap);
}
flow -= delta;
result += delta * potential[dst];
for (int v = dst; v != src; v = prev_v[v]) {
edge_t<T> & e = graph[prev_v[v]][prev_e[v]]; // reference
e.cap -= delta;
graph[v][e.rev].cap += delta;
}
}
return result;
}
int main() {
int n; scanf("%d", &n);
vector<int> a(n), b(n); repeat (i, n) scanf("%d%d", &a[i], &b[i]);
map<int, int> compress;
repeat (i, n) {
compress.emplace(a[i], compress.size()); // nop if it already exists
compress.emplace(b[i], compress.size());
}
auto edge = [&](int i) { return compress.size() + i; };
const int src = compress.size() + n;
const int dst = compress.size() + n + 1;
vector<vector<edge_t<int> > > g(1 + compress.size() + n + 1);
for (auto it : compress) {
int compressed_a_i = it.second;
add_edge(g, src, compressed_a_i, 1, 0);
}
repeat (i, n) {
add_edge(g, compress[a[i]], edge(i), 1, - b[i]);
add_edge(g, compress[b[i]], edge(i), 1, - a[i]);
add_edge(g, edge(i), dst, 1, 0);
}
add_edge(g, src, dst, n, 0);
int result = - min_cost_flow_destructive(src, dst, n, g);
printf("%d\n", result);
return 0;
}