제출 #1124947

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

school

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

typedef long long ll;
const int INF = INT32_MAX;

struct E {
    int to, rev, cap, cost;
};

vector<vector<E>> g;

inline void add_e(int u, int v, int c, int 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<int, ll> mcf(int n, int src, int sink, int mf) {
    vector<int> pot(n, 0), dist(n, 0), prevv(n, -1), preve(n, -1);
    int flow = 0;
    ll cost = 0;

    while (flow < mf) {
        fill(dist.begin(), dist.end(), INF);
        dist[src] = 0;

        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        pq.emplace(0, src);

        while (!pq.empty()) {
            auto [d, u] = pq.top();
            pq.pop();
            if (d > dist[u]) continue;
            for (int i = 0; i < g[u].size(); ++i) {
                E &e = g[u][i];
                if (e.cap > 0 && dist[e.to] > dist[u] + e.cost + pot[u] - pot[e.to]) {
                    dist[e.to] = dist[u] + e.cost + pot[u] - pot[e.to];
                    prevv[e.to] = u;
                    preve[e.to] = i;
                    pq.emplace(dist[e.to], e.to);
                }
            }
        }

        if (dist[sink] == INF) break;

        for (int i = 0; i < n; i++) if (dist[i] < INF) pot[i] += dist[i];

        int add_flow = mf - flow, v = sink;
        while (v != src) {
            add_flow = min(add_flow, g[prevv[v]][preve[v]].cap);
            v = prevv[v];
        }

        flow += add_flow;
        cost += (ll)add_flow * pot[sink];

        v = sink;
        while (v != src) {
            E &e = g[prevv[v]][preve[v]];
            e.cap -= add_flow;
            g[v][e.rev].cap += add_flow;
            v = prevv[v];
        }
    }

    return {flow, cost};
}

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

    int n, m, s;
    cin >> n >> m >> s;

    int nodes = 3 + n + 1;
    int src = 0, mus = 1, spo = 2, sink = 3 + n;
    g.assign(nodes, vector<E>());

    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        int city = 3 + i;
        add_e(mus, city, 1, -a);
        add_e(spo, city, 1, -b);
        add_e(city, sink, 1, 0);
    }

    add_e(src, mus, m, 0);
    add_e(src, spo, s, 0);

    pair<int, ll> res = mcf(nodes, src, sink, m + s);
    cout << -res.second;
}

• Subtask 1: 35 / 100