Cod sursa(job #3376969)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 20 noiembrie 2026 18:19:03
Problema Cuplaj maxim de cost minim Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.05 kb
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll INF = 1LL << 60;

struct MinCostMaxFlow {
    struct Edge { int v; ll cap, cost; };
    vector<vector<int>> g;
    vector<Edge> e;
    MinCostMaxFlow(int n) : g(n) {}
    void add(int a, int b, ll cap, ll cost) {
        g[a].push_back(e.size());
        e.push_back({b, cap, cost});
        g[b].push_back(e.size());
        e.push_back({a, 0, -cost});
    }
    pair<ll, ll> run(int s, int t) {
        int n = g.size();
        if (s == t) return {0, 0};
        vector<ll> h(n, INF), dist(n);
        vector<int> p(n), pe(n);
        h[s] = 0;
        for (int k = 0; k < n; k++) {
            bool change = false;
            for (int u = 0; u < n; u++) {
                if (h[u] == INF) continue;
                for (int id : g[u]) {
                    auto &a = e[id];
                    if (a.cap && h[a.v] > h[u] + a.cost) {
                        h[a.v] = h[u] + a.cost;
                        change = true;
                    }
                }
            }
            if (!change) break;
        }
        for (ll &x : h) if (x == INF) x = 0;
        ll flow = 0, cost = 0;
        while (true) {
            fill(dist.begin(), dist.end(), INF);
            priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
            dist[s] = 0;
            pq.push({0, s});
            while (!pq.empty()) {
                auto [d, u] = pq.top(); pq.pop();
                if (d != dist[u]) continue;
                for (int id : g[u]) {
                    auto &a = e[id];
                    if (!a.cap) continue;
                    ll nd = d + a.cost + h[u] - h[a.v];
                    if (nd < dist[a.v]) {
                        dist[a.v] = nd;
                        p[a.v] = u;
                        pe[a.v] = id;
                        pq.push({nd, a.v});
                    }
                }
            }
            if (dist[t] == INF) break;
            for (int i = 0; i < n; i++)
                if (dist[i] != INF) h[i] += dist[i];
            ll f = INF;
            for (int v = t; v != s; v = p[v])
                f = min(f, e[pe[v]].cap);
            for (int v = t; v != s; v = p[v]) {
                int id = pe[v];
                e[id].cap -= f;
                e[id ^ 1].cap += f;
                cost += f * e[id].cost;
            }
            flow += f;
        }
        return {flow, cost};
    }
};

int main() {
    ifstream fin("cmcm.in");
    ofstream fout("cmcm.out");

    int n, m, k;
    fin >> n >> m >> k;
    int s = 0, t = n + m + 1;
    MinCostMaxFlow d(t + 1);

    for (int i = 1; i <= n; i++) d.add(s, i, 1, 0);
    for (int j = 1; j <= m; j++) d.add(n + j, t, 1, 0);

    vector<int> ids(k);
    for (int i = 0; i < k; i++) {
        int a, b, cost;
        fin >> a >> b >> cost;
        ids[i] = d.e.size();
        d.add(a, n + b, 1, cost);
    }

    auto [flow, cost] = d.run(s, t);
    fout << flow << ' ' << cost << '\n';
    for (int i = 0; i < k; i++)
        if (d.e[ids[i]].cap == 0) fout << i + 1 << ' ';
    fout << '\n';
}