// // 3 変数劣モジュラ関数のグラフ表現 // // verified (3 変数は未 verify): // 競プロ典型 90 問 040 - Get More Money(★7) // https://atcoder.jp/contests/typical90/tasks/typical90_an // // AtCoder ARC 085 E - MUL (for basid psp) // https://atcoder.jp/contests/arc085/tasks/arc085_c // // AtCoder ABC 259 G - Grid Card Game (for basid psp) // https://atcoder.jp/contests/abc259/tasks/abc259_g // // AtCoder ABC 326 G - Unlock Achievement (for all-true profit) // https://atcoder.jp/contests/abc326/tasks/abc326_g // // AtCoder ABC 225 G - X (for xi = xj = 1 profit) // https://atcoder.jp/contests/abc225/tasks/abc225_g // // AOJ 2903 Board (for general 2-variable submodular function) // https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2903 // #include using namespace std; // 1, 2, 3-variable submodular optimization /* N 個の bool 変数 x_0, x_1, ..., x_{N-1} について、以下の形のコストが定められたときの最小コストを求める ・1 変数 xi に関するコスト (1 変数劣モジュラ関数) xi = F のときのコスト, xi = T のときのコスト ・2 変数 xi, xj 間の関係性についてのコスト (2 変数劣モジュラ関数)   (xi, xj) = (F, F): コスト A   (xi, xj) = (F, T): コスト B   (xi, xj) = (T, F): コスト C   (xi, xj) = (T, T): コスト D  (ただし、B + C >= A + D でなければならない) ・よくある例は、A = B = D = 0, C >= 0 の形である (特に関数化している) ・この場合は、特に Project Selection Problem と呼ばれ、俗に「燃やす埋める」などとも呼ばれる ・xi = T, xj = F のときにコスト C がかかる ・他に面白い例として、A = B = C = 0, D <= 0 の形もある (これも関数化している) ・xi = T, xj = T のときに (-D) の利得が得られる ・3 変数 xi, xj, xk 間の関係性についてのコスト (3 変数劣モジュラ関数)   (xi, xj, xk) = (F, F, F): コスト A   (xi, xj, xk) = (F, F, T): コスト B   (xi, xj, xk) = (F, T, F): コスト C   (xi, xj, xk) = (F, T, T): コスト D   (xi, xj, xk) = (T, F, F): コスト E   (xi, xj, xk) = (T, F, T): コスト F   (xi, xj, xk) = (T, T, F): コスト G   (xi, xj, xk) = (T, T, T): コスト H */ // 1, 2, 3-variable submodular optimization template struct ThreeVariableSubmodularOpt { // constructors ThreeVariableSubmodularOpt() : N(2), S(0), T(0), OFFSET(0) {} ThreeVariableSubmodularOpt(int n, COST inf = numeric_limits::max() / 2) : N(n), S(n), T(n + 1), OFFSET(0), INF(inf), list(n + 2) {} // initializer void init(int n, COST inf = numeric_limits::max() / 2) { N = n, S = n, T = n + 1; OFFSET = 0, INF = inf; list.clear(); list.resize(N + 2); pos.clear(); } // add constant cost void add_cost(COST cost) { OFFSET += cost; } // add 1-variable submodular function void add_single_cost(int xi, COST false_cost, COST true_cost) { assert(0 <= xi && xi < N); if (false_cost >= true_cost) { OFFSET += true_cost; if (false_cost - true_cost > 0) add_edge(S, xi, false_cost - true_cost); } else { OFFSET += false_cost; add_edge(xi, T, true_cost - false_cost); } } void add_single_cost_01(int xi, COST false_cost, COST true_cost) { add_single_cost(xi, false_cost, true_cost); } void add_single_cost_10(int xi, COST false_cost, COST true_cost) { add_single_cost(xi, true_cost, false_cost); } // add "project selection" constraint // xi = T, xj = F: strictly prohibited void add_psp_constraint(int xi, int xj) { assert(0 <= xi && xi < N); assert(0 <= xj && xj < N); assert(xi != xj); add_edge(xi, xj, INF); } void add_psp_constraint_01(int xi, int xj) { add_psp_constraint(xj, xi); } void add_psp_constraint_10(int xi, int xj) { add_psp_constraint(xi, xj); } // add "project selection" penalty // xi = T, xj = F: cost C void add_psp_penalty(int xi, int xj, COST C) { assert(0 <= xi && xi < N); assert(0 <= xj && xj < N); assert(xi != xj); assert(C >= 0); if (C > 0) add_edge(xi, xj, C); } void add_psp_penalty_01(int xi, int xj, COST C) { add_psp_penalty(xj, xi, C); } void add_psp_penalty_10(int xi, int xj, COST C) { add_psp_penalty(xi, xj, C); } // add both True profit // xi = T, xj = T: profit P (cost -P) void add_both_true_profit(int xi, int xj, COST P) { assert(0 <= xi && xi < N); assert(0 <= xj && xj < N); assert(xi != xj); assert(P >= 0); OFFSET -= P; if (P > 0) add_edge(S, xi, P); if (P > 0) add_edge(xi, xj, P); } // add both False profit // xi = F, xj = F: profit P (cost -P) void add_both_false_profit(int xi, int xj, COST P) { assert(0 <= xi && xi < N); assert(0 <= xj && xj < N); assert(xi != xj); assert(P >= 0); OFFSET -= P; if (P > 0) add_edge(xj, T, P); if (P > 0) add_edge(xi, xj, P); } // add general 2-variable submodular function // (xi, xj) = (F, F): A, (F, T): B // (xi, xj) = (T, F): C, (T, T): D void add_submodular_function(int xi, int xj, COST A, COST B, COST C, COST D) { assert(0 <= xi && xi < N); assert(0 <= xj && xj < N); assert(xi != xj); assert(B + C >= A + D); // assure submodular function OFFSET += A; add_single_cost(xi, 0, D - B); add_single_cost(xj, 0, B - A); if (B + C - A - D > 0) add_psp_penalty(xi, xj, B + C - A - D); } // add all True profit // y = F: not gain profit (= cost is P), T: gain profit (= cost is 0) // y: T, xi: F is prohibited void add_all_true_profit(const vector &xs, COST P) { assert(P >= 0); int y = (int)list.size(); list.resize(y + 1); OFFSET -= P; add_edge(S, y, P); for (auto xi : xs) { assert(xi >= 0 && xi < N); add_edge(y, xi, INF); } } // add all False profit // y = F: gain profit (= cost is 0), T: not gain profit (= cost is P) // xi = T, y = F is prohibited void add_all_false_profit(const vector &xs, COST P) { assert(P >= 0); int y = (int)list.size(); list.resize(y + 1); OFFSET -= P; add_edge(y, T, P); for (auto xi : xs) { assert(xi >= 0 && xi < N); add_edge(xi, y, INF); } } // add general 3-variable submodular function // (xi, xj, xk) = (F, F, F): cost A // (xi, xj, xk) = (F, F, T): cost B // (xi, xj, xk) = (F, T, F): cost C // (xi, xj, xk) = (F, T, T): cost D // (xi, xj, xk) = (T, F, F): cost E // (xi, xj, xk) = (T, F, T): cost F // (xi, xj, xk) = (T, T, F): cost G // (xi, xj, xk) = (T, T, T): cost H void add_submodular_function(int xi, int xj, int xk, COST A, COST B, COST C, COST D, COST E, COST F, COST G, COST H) { assert(0 <= xi && xi < N); assert(0 <= xj && xj < N); assert(0 <= xk && xk < N); COST P = (A + D + F + G) - (B + C + E + H); COST P12 = (C + E) - (A + G), P13 = (D + G) - (C + H); COST P21 = (D + F) - (B + H), P23 = (B + C) - (A + D); COST P31 = (B + E) - (A + F), P32 = (F + G) - (E + H); assert(P12 >= 0 && P21 >= 0); assert(P23 >= 0 && P32 >= 0); assert(P31 >= 0 && P13 >= 0); if (P >= 0) { OFFSET += A; add_single_cost(xi, 0, F - B); add_single_cost(xj, 0, G - E); add_single_cost(xk, 0, D - C); add_psp_penalty(xj, xi, P12); add_psp_penalty(xk, xj, P23); add_psp_penalty(xi, xk, P31); add_all_true_profit({xi, xj, xk}, P); } else { OFFSET += H; add_single_cost(xi, C - G, 0); add_single_cost(xj, B - D, 0); add_single_cost(xk, E - F, 0); add_psp_penalty(xi, xj, P21); add_psp_penalty(xj, xk, P32); add_psp_penalty(xk, xi, P13); add_all_false_profit({xi, xj, xk}, -P); } } // solve COST solve() { return dinic() + OFFSET; } // reconstrcut the optimal assignment vector reconstruct() { vector res(N, false), seen(list.size(), false); queue que; seen[S] = true; que.push(S); while (!que.empty()) { int v = que.front(); que.pop(); for (const auto &e : list[v]) { if (e.cap > 0 && !seen[e.to]) { if (e.to < N) res[e.to] = true; seen[e.to] = true; que.push(e.to); } } } return res; } // debug friend ostream& operator << (ostream& s, const ThreeVariableSubmodularOpt &tvs) { const auto &edges = tvs.get_edges(); for (const auto &e : edges) s << e << endl; return s; } private: // edge class struct Edge { // core members int rev, from, to; COST cap; // constructor Edge(int r, int f, int t, COST c) : rev(r), from(f), to(t), cap(c) {} // debug friend ostream& operator << (ostream& s, const Edge& e) { return s << e.from << "->" << e.to << '(' << e.cap << ')'; } }; // inner data int N, S, T; COST OFFSET, INF; vector> list; vector> pos; // add edge Edge &get_rev_edge(const Edge &e) { return list[e.to][e.rev]; } Edge &get_edge(int i) { return list[pos[i].first][pos[i].second]; } const Edge &get_edge(int i) const { return list[pos[i].first][pos[i].second]; } vector get_edges() const { vector edges; for (int i = 0; i < (int)pos.size(); ++i) { edges.push_back(get_edge(i)); } return edges; } void add_edge(int from, int to, COST cap) { if (cap <= 0) return; pos.emplace_back(from, (int)list[from].size()); list[from].push_back(Edge((int)list[to].size(), from, to, cap)); list[to].push_back(Edge((int)list[from].size() - 1, to, from, 0)); } // Dinic's algorithm COST dinic(COST limit_flow) { COST current_flow = 0; vector level((int)list.size(), -1), iter((int)list.size(), 0); queue que; // Dinic BFS auto bfs = [&]() -> void { fill(level.begin(), level.end(), -1); level[S] = 0; while (!que.empty()) que.pop(); que.push(S); while (!que.empty()) { int v = que.front(); que.pop(); for (const Edge &e : list[v]) { if (level[e.to] < 0 && e.cap > 0) { level[e.to] = level[v] + 1; if (e.to == T) return; que.push(e.to); } } } }; // Dinic DFS auto dfs = [&](auto self, int v, COST up_flow) { if (v == S) return up_flow; COST res_flow = 0; for (int &i = iter[v]; i < (int)list[v].size(); i++) { Edge &e = list[v][i], &re = get_rev_edge(e); if (level[v] <= level[e.to] || re.cap <= 0) continue; COST flow = self(self, e.to, min(up_flow - res_flow, re.cap)); if (flow <= 0) continue; res_flow += flow; e.cap += flow, re.cap -= flow; if (res_flow == up_flow) return res_flow; } level[v] = (int)list.size(); return res_flow; }; // flow while (current_flow < limit_flow) { bfs(); if (level[T] < 0) break; fill(iter.begin(), iter.end(), 0); while (current_flow < limit_flow) { COST flow = dfs(dfs, T, limit_flow - current_flow); if (flow <= 0) break; current_flow += flow; } } return current_flow; }; COST dinic() { return dinic(numeric_limits::max() / 2); } }; //------------------------------// // Examples //------------------------------// int main() { long long N, M; cin >> N >> M; vector A(N), B(M); for (int i = 0; i < N; i++) cin >> A[i]; for (int i = 0; i < M; i++) cin >> B[i]; vector> C(M); for (int i = 0; i < M; i++) { int K; cin >> K; C[i].resize(K); for (int j = 0; j < K; j++) cin >> C[i][j], C[i][j]--; } ThreeVariableSubmodularOpt opt(N); for (int i = 0; i < N; i++) opt.add_single_cost_10(i, A[i], 0); for (int i = 0; i < M; i++) opt.add_all_true_profit(C[i], B[i]); cout << -opt.solve() << endl; }