library
This documentation is automatically generated by online-judge-tools/verification-helper
K-Project Selection
(Algorithm/kprojectselection.hpp)
- View this file on GitHub
- Last update: 2024-04-29 14:20:00+09:00
- Include:
#include "Algorithm/kprojectselection.hpp"
Depends on
Maximum Flow
(Graph/maxflow.hpp)
Code
#pragma once
#include "Algorithm/projectselection.hpp"
template <typename Cost> struct KProjectSelection {
static constexpr Cost LIM = std::numeric_limits<Cost>::max() / 2;
int n;
vector<int> Ks;
vector<vector<int>> pos;
ProjectSelection<Cost> psp;
KProjectSelection() {}
KProjectSelection(vector<int> &Ks) : n(SZ(Ks)), Ks(Ks), pos(n) {
int now = 0;
rep(i, 0, n) {
pos[i].resize(Ks[i]);
rep(j, 1, Ks[i]) pos[i][j] = now++;
}
psp = ProjectSelection<Cost>(now);
rep(i, 0, n) {
rep(j, 1, Ks[i] - 1) psp.add_cost_10(pos[i][j], pos[i][j + 1], LIM);
}
}
void add_cost(Cost cost) {
psp.add_cost(cost);
}
void add_profit(Cost profit) {
psp.add_profit(profit);
}
void add_cost(int i, vector<Cost> &cost) {
assert(SZ(cost) == Ks[i]);
psp.add_cost(cost.back());
rep(j, 1, Ks[i]) {
psp.add_cost(pos[i][j], {0, cost[j - 1] - cost[j]});
}
}
void add_profit(int i, vector<Cost> &profit) {
for (auto &x : profit)
x = -x;
add_cost(i, profit);
}
void add_cost(int i, int j, vector<vector<Cost>> &cost) {
assert(SZ(cost) == Ks[i]);
vector<Cost> ibase(Ks[i]), jbase(Ks[j]);
rep(x, 0, Ks[i]) {
assert(SZ(cost[x]) == Ks[j]);
ibase[x] = cost[x][0];
rep(y, 0, Ks[j]) cost[x][y] -= ibase[x];
}
rep(y, 0, Ks[j]) {
jbase[y] = cost[0][y];
rep(x, 0, Ks[i]) cost[x][y] -= jbase[y];
}
add_cost(i, ibase);
add_cost(j, jbase);
rep(x, 1, Ks[i]) rep(y, 1, Ks[j]) {
Cost add = cost[x][y] - cost[x][y - 1] - cost[x - 1][y] +
cost[x - 1][y - 1];
assert(add <= 0);
psp.add_profit_00(pos[i][x], pos[j][y], -add);
}
}
pair<Cost, vector<int>> minCost() {
auto [ret, ids] = psp.minCost();
vector<int> xs(n);
rep(i, 0, n) rep(j, 1, Ks[i]) {
if (ids[pos[i][j]] == 1)
break;
xs[i] = j;
}
return {ret, xs};
}
pair<Cost, vector<int>> maxProfit() {
auto ret = minCost();
ret.first = -ret.first;
return ret;
}
};
/**
* @brief K-Project Selection
*/#line 2 "Graph/maxflow.hpp"
struct MaxFlow {
struct Edge {
int to, rev;
ll cap;
};
int V;
vector<vector<Edge>> G;
vector<int> itr, level;
using P = pair<int, int>;
vector<P> es;
public:
MaxFlow() {}
MaxFlow(int V) : V(V) {
G.assign(V, vector<Edge>());
}
int add_vertex() {
G.push_back(vector<Edge>());
return V++;
}
void add_edge(int from, int to, ll cap) {
int fid = SZ(G[from]), tid = SZ(G[to]);
if (from == to)
tid++;
es.push_back({from, fid});
G[from].push_back({to, tid, cap});
G[to].push_back({from, fid, 0});
}
struct Type {
int from, to;
ll cap, recap;
};
Type get_edge(int i) {
auto [from, pos] = es[i];
auto e = G[from][pos];
auto re = G[e.to][e.rev];
return Type{from, e.to, e.cap, re.cap};
}
void bfs(int s) {
level.assign(V, -1);
queue<int> q;
level[s] = 0;
q.push(s);
while (!q.empty()) {
int v = q.front();
q.pop();
for (auto &e : G[v]) {
if (e.cap > 0 && level[e.to] < 0) {
level[e.to] = level[v] + 1;
q.push(e.to);
}
}
}
}
ll dfs(int v, int t, ll f) {
if (v == t)
return f;
for (int &i = itr[v]; i < (int)G[v].size(); i++) {
Edge &e = G[v][i];
if (e.cap > 0 && level[v] < level[e.to]) {
ll d = dfs(e.to, t, min(f, e.cap));
if (d > 0) {
e.cap -= d, G[e.to][e.rev].cap += d;
return d;
}
}
}
return 0;
}
ll run(int s, int t) {
ll ret = 0, f;
while (bfs(s), level[t] >= 0) {
itr.assign(V, 0);
while ((f = dfs(s, t, INF)) > 0)
ret += f;
}
return ret;
}
vector<int> cut() {
vector<int> ret(V);
rep(v, 0, V) if (level[v] < 0) ret[v] = 1;
return ret;
}
};
/**
* @brief Maximum Flow
*/
#line 3 "Algorithm/projectselection.hpp"
template <typename Cost> struct ProjectSelection {
using C1 = array<Cost, 2>;
using C2 = array<C1, 2>;
using P = pair<int, Cost>;
int orig, n, S, T;
vector<vector<P>> es;
Cost offset;
vector<C1> base;
ProjectSelection() {}
ProjectSelection(int _n)
: orig(_n), n(_n + 2), S(_n), T(_n + 1), es(n), offset(0), base(n) {}
void add_cost(Cost cost) {
offset += cost;
}
void add_profit(Cost profit) {
add_cost(-profit);
}
void add_cost(int i, C1 cost) {
base[i][0] += cost[0];
base[i][1] += cost[1];
}
void add_profit(int i, C1 profit) {
base[i][0] -= profit[0];
base[i][1] -= profit[1];
}
void add_cost_0(int i, Cost cost) {
add_cost(i, C1{cost, 0});
}
void add_cost_1(int i, Cost cost) {
add_cost(i, C1{0, cost});
}
void add_profit_0(int i, Cost profit) {
add_cost(i, C1{-profit, 0});
}
void add_profit_1(int i, Cost profit) {
add_cost(i, C1{0, -profit});
}
void add_cost(int i, int j, C2 cost) {
Cost A = cost[0][0], B = cost[0][1];
Cost C = cost[1][0], D = cost[1][1];
assert(B + C >= A + D);
add_cost(A);
add_cost(i, C1{0, B - A});
add_cost(j, C1{0, D - C});
add_cost_01(i, j, (B + C) - (A + D));
}
void add_profit(int i, int j, C2 profit) {
rep(x, 0, 2) rep(y, 0, 2) profit[x][y] = -profit[x][y];
add_cost(i, j, profit);
}
void add_cost_01(int i, int j, Cost cost) {
assert(cost >= 0);
if (cost)
es[i].push_back({j, cost});
}
void add_cost_10(int i, int j, Cost cost) {
add_cost_01(j, i, cost);
}
void add_profit_00(int i, int j, Cost profit) {
add_cost(i, j, C2{-profit, 0, 0, 0});
}
void add_profit_11(int i, int j, Cost profit) {
add_cost(i, j, C2{0, 0, 0, -profit});
}
void add_profit_all0(vector<int> &xs, Cost profit) {
assert(profit >= 0);
if (profit == 0)
return;
add_profit(profit);
es.push_back({});
es[S].push_back({n, profit});
for (auto &i : xs)
es[n].push_back({i, profit});
n++;
}
void add_profit_all1(vector<int> &xs, Cost profit) {
assert(profit >= 0);
if (profit == 0)
return;
add_profit(profit);
es.push_back({});
es[n].push_back({T, profit});
for (auto &i : xs)
es[i].push_back({n, profit});
n++;
}
pair<Cost, vector<int>> minCost() {
MaxFlow mf(n);
rep(i, 0, orig) {
C1 &cost = base[i];
if (cost[0] <= cost[1]) {
add_cost(cost[0]);
if (cost[1] > cost[0])
es[S].push_back({i, cost[1] - cost[0]});
} else {
add_cost(cost[1]);
es[i].push_back({T, cost[0] - cost[1]});
}
}
rep(v, 0, n) for (auto &[u, cost] : es[v]) {
mf.add_edge(v, u, cost);
}
Cost ret = offset + mf.run(S, T);
vector<int> cut = mf.cut();
cut.resize(orig);
return {ret, cut};
}
pair<Cost, vector<int>> maxProfit() {
auto ret = minCost();
ret.first = -ret.first;
return ret;
}
};
/**
* @brief Project Selection
*/
#line 3 "Algorithm/kprojectselection.hpp"
template <typename Cost> struct KProjectSelection {
static constexpr Cost LIM = std::numeric_limits<Cost>::max() / 2;
int n;
vector<int> Ks;
vector<vector<int>> pos;
ProjectSelection<Cost> psp;
KProjectSelection() {}
KProjectSelection(vector<int> &Ks) : n(SZ(Ks)), Ks(Ks), pos(n) {
int now = 0;
rep(i, 0, n) {
pos[i].resize(Ks[i]);
rep(j, 1, Ks[i]) pos[i][j] = now++;
}
psp = ProjectSelection<Cost>(now);
rep(i, 0, n) {
rep(j, 1, Ks[i] - 1) psp.add_cost_10(pos[i][j], pos[i][j + 1], LIM);
}
}
void add_cost(Cost cost) {
psp.add_cost(cost);
}
void add_profit(Cost profit) {
psp.add_profit(profit);
}
void add_cost(int i, vector<Cost> &cost) {
assert(SZ(cost) == Ks[i]);
psp.add_cost(cost.back());
rep(j, 1, Ks[i]) {
psp.add_cost(pos[i][j], {0, cost[j - 1] - cost[j]});
}
}
void add_profit(int i, vector<Cost> &profit) {
for (auto &x : profit)
x = -x;
add_cost(i, profit);
}
void add_cost(int i, int j, vector<vector<Cost>> &cost) {
assert(SZ(cost) == Ks[i]);
vector<Cost> ibase(Ks[i]), jbase(Ks[j]);
rep(x, 0, Ks[i]) {
assert(SZ(cost[x]) == Ks[j]);
ibase[x] = cost[x][0];
rep(y, 0, Ks[j]) cost[x][y] -= ibase[x];
}
rep(y, 0, Ks[j]) {
jbase[y] = cost[0][y];
rep(x, 0, Ks[i]) cost[x][y] -= jbase[y];
}
add_cost(i, ibase);
add_cost(j, jbase);
rep(x, 1, Ks[i]) rep(y, 1, Ks[j]) {
Cost add = cost[x][y] - cost[x][y - 1] - cost[x - 1][y] +
cost[x - 1][y - 1];
assert(add <= 0);
psp.add_profit_00(pos[i][x], pos[j][y], -add);
}
}
pair<Cost, vector<int>> minCost() {
auto [ret, ids] = psp.minCost();
vector<int> xs(n);
rep(i, 0, n) rep(j, 1, Ks[i]) {
if (ids[pos[i][j]] == 1)
break;
xs[i] = j;
}
return {ret, xs};
}
pair<Cost, vector<int>> maxProfit() {
auto ret = minCost();
ret.first = -ret.first;
return ret;
}
};
/**
* @brief K-Project Selection
*/