結果

問題 No.3201 Corporate Synergy
コンテスト
ユーザー iastm
提出日時 2026-01-04 06:12:16
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 2,804 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 8,492 ms
コンパイル使用メモリ 203,560 KB
実行使用メモリ 7,852 KB
最終ジャッジ日時 2026-01-04 06:12:29
合計ジャッジ時間 3,605 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 1
other AC * 9 WA * 11
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <tuple>
// #include <kotone/project_selection>
// https://github.com/amiast/cpp-utility

#ifndef KOTONE_PROJECT_SELECTION_HPP
#define KOTONE_PROJECT_SELECTION_HPP 1

#include <atcoder/maxflow>

namespace kotone {

// A minimal wrapper for solving project selection problems using flow network algorithm.
template <typename Cap> struct project_selection {
    atcoder::mf_graph<Cap> graph;
    int source, sink;

    // Constructs a flow network for the specified number of projects.
    project_selection(int num_projects) : graph(num_projects + 2), source(num_projects), sink(num_projects + 1) {}

    // Adds the specified cost if project `i` is assigned `b`.
    // Requires `0 <= i < num_projects`.
    // Requires `cost >= 0`.
    void add_single(int i, bool b, Cap cost) {
        if (b) graph.add_edge(i, sink, cost);
        else graph.add_edge(source, i, cost);
    }

    // Adds the specified cost if project `i` is assigned `true` and project `j` is assigned `false`.
    // Requires `0 <= i, j < num_projects`.
    // Requires `cost >= 0`.
    void add_pair(int i, int j, Cap cost) {
        graph.add_edge(i, j, cost);
    }

    // Finds an optimal assignment and returns the minimum cost.
    // This function should be called once after adding constraints to the flow network.
    Cap eval_cost() {
        return graph.flow(source, sink);
    }

    // Returns a vector of `bool` indicating the assignment of each project.
    // This function should be called after `eval_cost`.
    std::vector<bool> assignment() {
        std::vector<bool> result = graph.min_cut(source);
        result.pop_back();
        result.pop_back();
        return result;
    }
};

}  // namespace kotone

#endif  // KOTONE_PROJECT_SELECTION_HPP

int main() {
    int N;
    std::cin >> N;
    std::vector<int64_t> P(N);
    for (int64_t &p : P) std::cin >> p;
    int M;
    std::cin >> M;
    std::vector<std::pair<int, int>> edges(M);
    for (auto &[u, v] : edges) std::cin >> u >> v, u--, v--;
    int K;
    std::cin >> K;
    std::vector<std::tuple<int, int, int64_t>> bonus(K);
    for (auto &[a, b, s] : bonus) std::cin >> a >> b >> s, a--, b--;

    kotone::project_selection<int64_t> graph(N + K);
    int64_t revenue = 0;
    for (int i = 0; i < N; i++) {
        if (P[i] >= 0) {
            revenue += P[i];
            graph.add_single(i, false, P[i]);
        } else {
            graph.add_single(i, true, -P[i]);
        }
    }
    for (auto [u, v] : edges) graph.add_pair(v, u, 1LL << 60);
    for (int i = 0; i < K; i++) {
        auto [a, b, s] = bonus[i];
        revenue += s;
        graph.add_pair(i + N, a, 1LL << 60);
        graph.add_pair(i + N, b, 1LL << 60);
    }

    std::cout << revenue - graph.eval_cost() << std::endl;
}
0