結果

問題 No.957 植林
ユーザー kyoukyou
提出日時 2021-02-28 22:47:34
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 2,699 bytes
コンパイル時間 4,323 ms
コンパイル使用メモリ 242,036 KB
実行使用メモリ 45,436 KB
最終ジャッジ日時 2024-04-12 10:57:30
合計ジャッジ時間 15,227 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
13,764 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 1 ms
6,944 KB
testcase_03 AC 1,859 ms
35,060 KB
testcase_04 TLE -
testcase_05 AC 1,631 ms
35,820 KB
testcase_06 TLE -
testcase_07 AC 1,826 ms
33,348 KB
testcase_08 AC 429 ms
35,244 KB
testcase_09 AC 366 ms
36,348 KB
testcase_10 AC 580 ms
38,008 KB
testcase_11 AC 497 ms
35,260 KB
testcase_12 AC 520 ms
34,872 KB
testcase_13 AC 306 ms
31,644 KB
testcase_14 AC 400 ms
38,740 KB
testcase_15 AC 398 ms
35,000 KB
testcase_16 AC 324 ms
31,776 KB
testcase_17 AC 361 ms
33,856 KB
testcase_18 TLE -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
testcase_42 -- -
testcase_43 -- -
testcase_44 -- -
testcase_45 -- -
testcase_46 -- -
testcase_47 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'void add_edge(graph&, P&, P&, ll)':
main.cpp:24:47: warning: narrowing conversion of '(&(& G)->std::map<std::pair<int, int>, std::vector<edge> >::operator[]((*(const std::map<std::pair<int, int>, std::vector<edge> >::key_type*)(& to))))->std::vector<edge>::size()' from 'std::vector<edge>::size_type' {aka 'long unsigned int'} to 'll' {aka 'long long int'} [-Wnarrowing]
   24 |     G[from].push_back(edge{to, cap, G[to].size()});
      |                                     ~~~~~~~~~~^~
main.cpp:25:50: warning: narrowing conversion of '((&(& G)->std::map<std::pair<int, int>, std::vector<edge> >::operator[]((*(const std::map<std::pair<int, int>, std::vector<edge> >::key_type*)(& from))))->std::vector<edge>::size() - 1)' from 'std::vector<edge>::size_type' {aka 'long unsigned int'} to 'll' {aka 'long long int'} [-Wnarrowing]
   25 |     G[to].push_back(edge{from, 0, G[from].size() - 1});
      |                                   ~~~~~~~~~~~~~~~^~~

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>

#define rep(i, n) for (int i = 0; i < n; ++i)

using namespace std;
using namespace atcoder;
bool chmin(int& a, int b) { if (a > b) { a = b; return true; } return false; }
bool chmax(int& a, int b) { if (a < b) { a = b; return true; } return false; }
 
using ll = long long;
constexpr int INF = (int)2e9;
constexpr ll  INFll = (ll)9e18;
constexpr int MOD = 998244353;

using P = pair<int, int>;
struct edge { P to; ll cap, rev; };
using graph = map<P, vector<edge>>;

map<P, int> levels;
map<P, int> iter;

void add_edge(graph &G, P &from, P &to, ll cap) {
    G[from].push_back(edge{to, cap, G[to].size()});
    G[to].push_back(edge{from, 0, G[from].size() - 1});
}

void bfs(graph &G, P &s) {
    levels.clear();
    levels[s] = 0;
    queue<P> que;
    que.push(s);
    while (!que.empty()) {
        P p = que.front(); que.pop();
        for (auto e : G[p]) {
            if (e.cap > 0 && !levels.count(e.to)) {
                levels[e.to] = levels[p] + 1;
                que.push(e.to);
            }
        }
    }
}

ll dfs(graph &G, P &v, P &t, ll f) {
    if (v == t) return f;
    for (int &i = iter[v]; i < G[v].size(); ++i) {
        auto &e = G[v][i];
        if (e.cap > 0 && levels[v] < levels[e.to]) {
            auto d = dfs(G, 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 max_flow(graph &G, P &s, P &t) {
    ll flow = 0;
    for (;;) {
        bfs(G, s);
        if (!levels.count(t))
            return flow;
        iter.clear();
        ll f;
        while ((f = dfs(G, s, t, INF)) > 0) {
            flow += f;
        }
    }
}

P col(int w) {
    return P{-1, w};
}

P row(int h) {
    return P{h, -1};
}

int main() {
    int H, W; cin >> H >> W;
    vector<vector<int>> Gs(H, vector<int>(W, 0));
    for (int i = 0; i < H; ++i) for (int j = 0; j < W; ++j)
        cin >> Gs[i][j];
    vector<int> R(H), C(W);
    for (int i = 0; i < H; ++i) cin >> R[i];
    for (int i = 0; i < W; ++i) cin >> C[i];

    graph G;
    P s {-1, -1}, t {H, W};
    for (int h = 0; h < H; ++h)
    for (int w = 0; w < W; ++w) {
        P p = P{h,w}, r = row(h), c = col(w);
        add_edge(G, s, p, Gs[h][w]);
        add_edge(G, p, r, INFll);
        add_edge(G, p, c, INFll);
    }

    ll res = 0;
    for (int h = 0; h < H; ++h) {
        P r = row(h);
        add_edge(G, r, t, R[h]);
        res += R[h];
    }
    for (int w = 0; w < W; ++w) {
        P c = col(w);
        add_edge(G, c, t, C[w]);
        res += C[w];
    }
    res -= max_flow(G, s, t);
    cout << res << endl;
}
0