제출 #1350469

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1350469		Faisal_Saqib	Domino (COCI15_domino)	C++20	100 / 160	668 ms	589824 KiB

domino

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct Edge {
    int to, rev, cap;
    ll cost;
};

struct MCMF {
    int N;
    vector<vector<Edge>> g;

    MCMF(int n) : N(n), g(n) {}

    void addEdge(int s, int t, int cap, ll cost) {
        g[s].push_back({t, (int)g[t].size(), cap, cost});
        g[t].push_back({s, (int)g[s].size() - 1, 0, -cost});
    }

    pair<int, ll> maxCostMaxFlow(int s, int t, int maxf) {
        int flow = 0;
        ll cost = 0;

        vector<ll> dist(N);
        vector<int> inq(N), par_v(N), par_e(N);

        while (flow < maxf) {
            fill(dist.begin(), dist.end(), LLONG_MIN);
            fill(inq.begin(), inq.end(), 0);

            dist[s] = 0;
            queue<int> q;
            q.push(s);
            inq[s] = 1;

            // SPFA (maximize cost)
            while (!q.empty()) {
                int v = q.front();
                q.pop();
                inq[v] = 0;

                for (int i = 0; i < (int)g[v].size(); i++) {
                    Edge &e = g[v][i];
                    if (e.cap > 0 && dist[e.to] < dist[v] + e.cost) {
                        dist[e.to] = dist[v] + e.cost;
                        par_v[e.to] = v;
                        par_e[e.to] = i;
                        if (!inq[e.to]) {
                            q.push(e.to);
                            inq[e.to] = 1;
                        }
                    }
                }
            }

            // no more augmenting path
            if (dist[t] == LLONG_MIN) break;

            int addf = maxf - flow;

            // find bottleneck
            int v = t;
            while (v != s) {
                Edge &e = g[par_v[v]][par_e[v]];
                addf = min(addf, e.cap);
                v = par_v[v];
            }

            // apply flow
            v = t;
            while (v != s) {
                Edge &e = g[par_v[v]][par_e[v]];
                e.cap -= addf;
                g[v][e.rev].cap += addf;
                v = par_v[v];
            }

            flow += addf;
            cost += dist[t] * addf;
        }

        return {flow, cost};
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;
    ll tot=0;
    vector<vector<int>> a(n, vector<int>(n));
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> a[i][j];
            tot+=a[i][j];
        }
    }

    int V = n * n + 2;
    int S = n * n;
    int T = n * n + 1;

    MCMF mf(V);

    auto id = [&](int i, int j) {
        return i * n + j;
    };

    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {

            if ((i + j) % 2 == 1) {
                // black → from source
                mf.addEdge(S, id(i, j), 1, 0);

                for (int d = 0; d < 4; d++) {
                    int ni = i + dx[d];
                    int nj = j + dy[d];

                    if (ni < 0 || nj < 0 || ni >= n || nj >= n) continue;

                    // black → white
                    mf.addEdge(id(i, j), id(ni, nj), 1,
                               a[i][j] + a[ni][nj]);
                }
            } else {
                // white → sink
                mf.addEdge(id(i, j), T, 1, 0);
            }
        }
    }

    auto [flow, cost] = mf.maxCostMaxFlow(S, T, k);

    cout << tot-cost << "\n";

    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 10
• Subtask 6: 10 / 10
• Subtask 7: 0 / 10
• Subtask 8: 10 / 10
• Subtask 9: 0 / 10
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10
• Subtask 12: 0 / 10
• Subtask 13: 10 / 10
• Subtask 14: 10 / 10
• Subtask 15: 10 / 10
• Subtask 16: 0 / 10