#1104304 (C++17) No.3201 Corporate Synergy

• 問題: No.3201 Corporate Synergy
• ユーザー: theory_and_me
• 提出日時: 2025-07-12 04:47:56
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 2 ms / 2,000 ms
• コード長: 14,360 bytes
• コンパイル時間: 2,778 ms
• コンパイル使用メモリ: 211,388 KB
• 実行使用メモリ: 6,272 KB
• 最終ジャッジ日時: 2025-07-12 04:48:00
• 合計ジャッジ時間: 3,555 ms
• ジャッジサーバーID （参考情報）: judge4 / judge5

ファイルパターン	結果
sample	AC * 2
other	AC * 20

ソースコード

#include <bits/stdc++.h>
using namespace std;

#include <atcoder/maxflow>
using namespace atcoder;

#define rep_(i, a_, b_, a, b, ...) for (int i = (a), lim##i = (b); i < lim##i; ++i)
#define rep(i, ...) rep_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
#define drep_(i, a_, b_, a, b, ...) for (int i = (a) - 1, lim##i = (b); i >= lim##i; --i)
#define drep(i, ...) drep_(i, __VA_ARGS__, __VA_ARGS__, __VA_ARGS__, 0)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#ifdef LOCAL
void debug_out() {
    cerr << endl;
}
template <class Head, class... Tail> void debug_out(Head H, Tail... T) {
    cerr << ' ' << H;
    debug_out(T...);
}
#define debug(...) cerr << 'L' << __LINE__ << " [" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define dump(x) cerr << 'L' << __LINE__ << " " << #x << " = " << (x) << endl
#else
#define debug(...) (void(0))
#define dump(x) (void(0))
#endif
using ll = long long;
using ld = long double;
template <class T> using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>;
template <class T> vector<T> make_vec(size_t n, T a) {
    return vector<T>(n, a);
}
template <class... Ts> auto make_vec(size_t n, Ts... ts) {
    return vector<decltype(make_vec(ts...))>(n, make_vec(ts...));
}
template <class T> inline void fin(const T x) {
    cout << x << '\n';
    exit(0);
}
template <class T> inline void deduplicate(vector<T> &a) {
    sort(all(a));
    a.erase(unique(all(a)), a.end());
}
template <class T> inline bool chmin(T &a, const T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> inline bool chmax(T &a, const T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> inline int sz(const T &x) {
    return x.size();
}
template <class T> inline int count_between(const vector<T> &a, T l, T r) {
    return lower_bound(all(a), r) - lower_bound(all(a), l);
}
template <class T1, class T2> istream &operator>>(istream &is, pair<T1, T2> &p) {
    is >> p.first >> p.second;
    return is;
}
template <class T1, class T2> ostream &operator<<(ostream &os, pair<T1, T2> &p) {
    os << '(' << p.first << ", " << p.second << ')';
    return os;
}
template <class T, size_t n> istream &operator>>(istream &is, array<T, n> &v) {
    for (auto &e : v) is >> e;
    return is;
}
template <class T, size_t n> ostream &operator<<(ostream &os, array<T, n> &v) {
    for (auto &e : v) os << e << ' ';
    return os;
}
template <class T> istream &operator>>(istream &is, vector<T> &v) {
    for (auto &e : v) is >> e;
    return is;
}
template <class T> ostream &operator<<(ostream &os, vector<T> &v) {
    for (auto &e : v) os << e << ' ';
    return os;
}
template <class T> istream &operator>>(istream &is, deque<T> &v) {
    for (auto &e : v) is >> e;
    return is;
}
template <class T> ostream &operator<<(ostream &os, deque<T> &v) {
    for (auto &e : v) os << e << ' ';
    return os;
}
inline ll floor_div(ll x, ll y) {
    if (y < 0) x = -x, y = -y;
    return x >= 0 ? x / y : (x - y + 1) / y;
}
inline ll ceil_div(ll x, ll y) {
    if (y < 0) x = -x, y = -y;
    return x >= 0 ? (x + y - 1) / y : x / y;
}
inline int floor_log2(const ll x) {
    assert(x > 0);
    return 63 - __builtin_clzll(x);
}
inline int ceil_log2(const ll x) {
    assert(x > 0);
    return (x == 1) ? 0 : 64 - __builtin_clzll(x - 1);
}
inline int popcount(const ll x) {
    return __builtin_popcountll(x);
}
struct fast_ios {
    fast_ios() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(20);
    };
} fast_ios;

// 時間計測
auto system_now = std::chrono::system_clock::now();
int check_time() {
    auto now = std::chrono::system_clock::now();
    return std::chrono::duration_cast<std::chrono::milliseconds>(now - system_now).count();
}

// 乱数
struct Xorshift {
    uint32_t x = 123456789, y = 362436069, z = 521288629, w = 88675123;

    uint32_t rand_int() {
        uint32_t t = x ^ (x << 11);
        x = y;
        y = z;
        z = w;
        return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
    }

    // 0以上mod未満の整数を乱択
    uint32_t rand_int(uint32_t mod) {
        return rand_int() % mod;
    }

    // l以上r未満の整数を乱択
    uint32_t rand_int(uint32_t l, uint32_t r) {
        assert(l < r);
        return l + rand_int(r - l);
    }

    // 0以上1以下の実数を乱沢
    double rand_double() {
        return (double)rand_int() / UINT32_MAX;
    }
};
Xorshift xor_shift;

// constexpr int INF = numeric_limits<int>::max() >> 2;
// constexpr ll INFll = numeric_limits<ll>::max() >> 2;
// constexpr ld EPS = 1e-10;
// const ld PI = acos(-1.0);
// using mint = modint998244353;
// using mint = modint1000000007;
// using mint = modint;
// using Vm = V<mint>; using VVm = VV<mint>;

/*
 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) の利得が得られる
 */

#include <bits/stdc++.h>
using namespace std;

// 2-variable submodular optimization
template <class COST> struct TwoVariableSubmodularOpt {
    // constructors
    TwoVariableSubmodularOpt()
        : N(2), S(0), T(0), OFFSET(0) {
    }
    TwoVariableSubmodularOpt(int n, COST inf = 0)
        : N(n), S(n), T(n + 1), OFFSET(0), INF(inf), list(n + 2) {
    }

    // initializer
    void init(int n, COST inf = 0) {
        N = n, S = n, T = n + 1;
        OFFSET = 0, INF = inf;
        list.assign(N + 2, Edge());
        pos.clear();
    }

    // add 1-Variable submodular functioin
    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;
            add_edge(S, xi, false_cost - true_cost);
        } else {
            OFFSET += false_cost;
            add_edge(xi, T, 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);
        add_edge(xi, xj, INF);
    }

    // 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(C >= 0);
        add_edge(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(P >= 0);
        OFFSET -= P;
        add_edge(S, xi, P);
        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(P >= 0);
        OFFSET -= P;
        add_edge(xj, T, P);
        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(B + C >= A + D);  // assure submodular function
        OFFSET += A;
        add_single_cost(xi, 0, D - B);
        add_single_cost(xj, 0, B - A);
        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<int> &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<int> &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);
        }
    }

    // solve
    COST solve() {
        return dinic() + OFFSET;
    }

    // reconstrcut the optimal assignment
    vector<bool> reconstruct() {
        vector<bool> res(N, false), seen(list.size(), false);
        queue<int> 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 && !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 TwoVariableSubmodularOpt &G) {
        const auto &edges = G.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, icap, flow;

        // constructor
        Edge(int r, int f, int t, COST c)
            : rev(r), from(f), to(t), cap(c), icap(c), flow(0) {
        }
        void reset() {
            cap = icap, flow = 0;
        }

        // debug
        friend ostream &operator<<(ostream &s, const Edge &E) {
            return s << E.from << "->" << E.to << '(' << E.flow << '/' << E.icap << ')';
        }
    };

    // inner data
    int N, S, T;
    COST OFFSET, INF;
    vector<vector<Edge>> list;
    vector<pair<int, int>> pos;

    // add edge
    Edge &get_rev_edge(const Edge &e) {
        if (e.from != e.to)
            return list[e.to][e.rev];
        else
            return list[e.to][e.rev + 1];
    }
    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<Edge> get_edges() const {
        vector<Edge> 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) 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<int> level((int)list.size(), -1), iter((int)list.size(), 0);

        // Dinic BFS
        auto bfs = [&]() -> void {
            level.assign((int)list.size(), -1);
            level[S] = 0;
            queue<int> que;
            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 == T) 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] || e.cap == 0) continue;
                COST flow = self(self, e.to, min(up_flow - res_flow, e.cap));
                if (flow <= 0) continue;
                res_flow += flow;
                e.cap -= flow, e.flow += flow;
                re.cap += flow, re.flow -= flow;
                if (res_flow == up_flow) break;
            }
            return res_flow;
        };

        // flow
        while (current_flow < limit_flow) {
            bfs();
            if (level[T] < 0) break;
            iter.assign((int)iter.size(), 0);
            while (current_flow < limit_flow) {
                COST flow = dfs(dfs, S, limit_flow - current_flow);
                if (!flow) break;
                current_flow += flow;
            }
        }
        return current_flow;
    };
    COST dinic() {
        return dinic(numeric_limits<COST>::max());
    }
};

int main() {
    int N;
    cin >> N;
    vector<int> P(N);
    rep(i, N) cin >> P[i];

    int M;
    cin >> M;
    vector<int> U(M), V(M);
    rep(i, M) {
        cin >> U[i] >> V[i];
        --U[i], --V[i];
    }

    int K;
    cin >> K;
    vector<int> A(K), B(K), S(K);
    rep(i, K) {
        cin >> A[i] >> B[i] >> S[i];
        --A[i], --B[i];
    }

    const long long INF = 1LL << 55;
    TwoVariableSubmodularOpt<ll> G(N, INF);
    rep(i, N) {
        G.add_single_cost(i, 0, -P[i]);
    }
    rep(i, M) {
        G.add_psp_constraint(V[i], U[i]);
    }
    rep(i, K) {
        G.add_both_true_profit(A[i], B[i], S[i]);
    }

    cout << -G.solve() << endl;
    vector<bool> ans = G.reconstruct();

    return 0;
}