제출 #1124926

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1124926		seiryuu	학교 설립 (IZhO13_school)	C++20	35 / 100	2098 ms	85852 KiB

school

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

typedef long long ll;
const ll INF = 1e18;

struct E {
    int t, r;
    ll c, w;
};

void add(vector<vector<E>> &g, int u, int v, ll c, ll w) {
    g[u].push_back({v, (int)g[v].size(), c, w});
    g[v].push_back({u, (int)g[u].size() - 1, 0, -w});
}

pair<ll, ll> mcmf(vector<vector<E>> &g, int s, int t) {
    int n = g.size();
    ll f = 0, c = 0;
    vector<ll> p(n, 0);
    while (true) {
        priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> q;
        vector<ll> d(n, INF);
        vector<int> pv(n, -1), pe(n, -1);
        d[s] = 0;
        q.push({0, s});
        while (!q.empty()) {
            auto [dist, u] = q.top();
            q.pop();
            if (dist > d[u]) continue;
            for (int i = 0; i < g[u].size(); ++i) {
                E &e = g[u][i];
                if (e.c > 0 && d[e.t] > d[u] + e.w + p[u] - p[e.t]) {
                    d[e.t] = d[u] + e.w + p[u] - p[e.t];
                    pv[e.t] = u;
                    pe[e.t] = i;
                    q.push({d[e.t], e.t});
                }
            }
        }
        if (d[t] == INF) break;
        for (int i = 0; i < n; ++i) if (d[i] < INF) p[i] += d[i];
        ll af = INF, v = t;
        while (v != s) {
            int u = pv[v], i = pe[v];
            af = min(af, g[u][i].c);
            v = u;
        }
        f += af;
        c += af * p[t];
        v = t;
        while (v != s) {
            int u = pv[v], i = pe[v];
            g[u][i].c -= af;
            g[v][g[u][i].r].c += af;
            v = u;
        }
    }
    return {f, c};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m, s;
    cin >> n >> m >> s;
    int src = 0, mus = 1, spo = 2, snk = 3 + n;
    vector<vector<E>> g(4 + n);
    vector<pair<int, int>> c(n);
    for (int i = 0; i < n; ++i) cin >> c[i].first >> c[i].second;
    add(g, src, mus, m, 0);
    add(g, src, spo, s, 0);
    for (int i = 0; i < n; ++i) {
        int u = 3 + i;
        add(g, mus, u, 1, -c[i].first);
        add(g, spo, u, 1, -c[i].second);
        add(g, u, snk, 1, 0);
    }
    auto res = mcmf(g, src, snk);
    if (res.first != m + s) {
        cout << "0";
        return 0;
    }
    cout << -res.second;
}

• Subtask 1: 35 / 100