提出 #23390951

---

ソースコード 拡げる

#include <iostream>
#include <vector>
#include <atcoder/maxflow>
using namespace std;

int get_index() {
    static int id = -1;
    id += 1;
    return id;
}

int main() {
    int H, W, N;
    cin >> H >> W >> N;
    vector<int> A(N), B(N), C(N), D(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i] >> B[i] >> C[i] >> D[i];
        A[i] -= 1;
        B[i] -= 1;
    }
    const int src = get_index();
    const int dst = get_index();
    vector<int> row(H), col(W);
    for (int i = 0; i < H; ++i) {
        row[i] = get_index();
    }
    for (int i = 0; i < W; ++i) {
        col[i] = get_index();
    }
    vector<int> token_r(N), token_c(N);
    for (int i = 0; i < N; ++i) {
        token_r[i] = get_index();
        token_c[i] = get_index();
    }
    atcoder::mf_graph<int> graph(get_index());
    for (int i = 0; i < H; ++i) {
        graph.add_edge(src, row[i], 1);
    }
    for (int i = 0; i < W; ++i) {
        graph.add_edge(col[i], dst, 1);
    }
    for (int i = 0; i < N; ++i) {
        for (int j = A[i]; j < C[i]; ++j) {
            graph.add_edge(row[j], token_r[i], 1);
        }
        graph.add_edge(token_r[i], token_c[i], 1);
        for (int j = B[i]; j < D[i]; ++j) {
            graph.add_edge(token_c[i], col[j], 1);
        }
    }
    cout << graph.flow(src, dst) << '\n';
}

提出情報

ジャッジ結果