結果

問題 No.957 植林
コンテスト
ユーザー kyou
提出日時 2021-02-28 22:47:34
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,699 bytes
コンパイル時間 3,612 ms
コンパイル使用メモリ 248,076 KB
実行使用メモリ 38,728 KB
最終ジャッジ日時 2024-10-02 22:37:45
合計ジャッジ時間 15,246 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13 TLE * 3 -- * 29
権限があれば一括ダウンロードができます
コンパイルメッセージ
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