結果

問題 No.957 植林
コンテスト
ユーザー iastm
提出日時 2026-01-04 06:59:53
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 388 ms / 2,000 ms
コード長 2,524 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,189 ms
コンパイル使用メモリ 194,760 KB
実行使用メモリ 9,020 KB
最終ジャッジ日時 2026-01-04 07:00:06
合計ジャッジ時間 12,462 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
// #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 H, W;
    std::cin >> H >> W;
    kotone::project_selection<int64_t> graph(H + W);
    int64_t revenue = 0;
    for (int i = 0; i < H; i++) {
        int64_t cost = 0;
        for (int j = 0; j < W; j++) {
            int64_t g;
            std::cin >> g;
            cost += g;
            graph.add_pair(j + H, i, g);
        }
        graph.add_single(i, true, cost);
    }
    for (int i = 0; i < H; i++) {
        int64_t r;
        std::cin >> r;
        revenue += r;
        graph.add_single(i, false, r);
    }
    for (int j = 0; j < W; j++) {
        int64_t c;
        std::cin >> c;
        revenue += c;
        graph.add_single(j + H, false, c);
    }
    std::cout << revenue - graph.eval_cost() << std::endl;
}
0