結果

問題 No.957 植林
ユーザー kyoukyou
提出日時 2021-02-28 22:10:10
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,766 bytes
コンパイル時間 4,291 ms
コンパイル使用メモリ 248,004 KB
実行使用メモリ 24,268 KB
最終ジャッジ日時 2024-10-02 22:32:25
合計ジャッジ時間 10,459 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
testcase_37 WA -
testcase_38 WA -
testcase_39 WA -
testcase_40 WA -
testcase_41 AC 110 ms
24,140 KB
testcase_42 AC 109 ms
24,012 KB
testcase_43 AC 134 ms
24,264 KB
testcase_44 WA -
testcase_45 AC 2 ms
5,248 KB
testcase_46 WA -
testcase_47 WA -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'void add_edge(graph&, P, P, int)':
main.cpp:21:47: warning: narrowing conversion of '(&(& G)->std::map<std::pair<int, int>, std::vector<edge> >::operator[](to))->std::vector<edge>::size()' from 'std::vector<edge>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   21 |     G[from].push_back(edge{to, cap, G[to].size()});
      |                                     ~~~~~~~~~~^~
main.cpp:22:50: warning: narrowing conversion of '((&(& G)->std::map<std::pair<int, int>, std::vector<edge> >::operator[](from))->std::vector<edge>::size() - 1)' from 'std::vector<edge>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   22 |     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; int cap, rev; };
using graph = map<P, vector<edge>>;

void add_edge(graph &G, P from, P to, int 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, map<P, int> &levels, P s) {
    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);
            }
        }
    }
}

int dfs(graph &G, map<P, int> &levels, map<P, int> &iter, P v, P t, int 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]) {
            int d = dfs(G, levels, iter, e.to, t, min(f, e.cap));
            if (d > 0) {
                e.cap -= d;
                G[e.to][e.rev].cap += d;
                return d;
            }
        }
    }
    return 0;
}

int max_flow(graph &G, P s, P t) {
    int flow = 0;
    for (;;) {
        map<P, int> levels;
        bfs(G, levels, s);
        if (!levels.count(t))
            return flow;
        map<P, int> iter;
        int f;
        while ((f = dfs(G, levels, iter, 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, INF);
        add_edge(G, p, c, INF);
    }

    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