Cod sursa(job #3233278)

Utilizator MirceaDonciuLicentaLicenta Mircea Donciu MirceaDonciuLicenta Data 2 iunie 2024 21:19:59
Problema Cuplaj maxim de cost minim Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.95 kb
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <cstring>
#include <fstream>

using namespace std;

const int INF = INT_MAX;

struct Edge {
    int from, to, capacity, cost, flow, reverse_index;
};

class MinCostMaxFlow {
public:
    MinCostMaxFlow(int n) : n(n), graph(n), potential(n, 0), dist(n), prev_vertex(n), prev_edge(n) {}

    void addEdge(int from, int to, int capacity, int cost) {
        graph[from].push_back({from, to, capacity, cost, 0, (int) graph[to].size()});
        graph[to].push_back({to, from, 0, -cost, 0, (int) graph[from].size() - 1});
    }

    pair<int, int> getMinCostMaxFlow(int source, int sink) {
        int flow = 0, cost = 0;
        while (bellmanFord(source, sink)) {
            int pushed_flow = INF;
            for (int v = sink; v != source; v = prev_vertex[v]) {
                pushed_flow = min(pushed_flow, graph[prev_vertex[v]][prev_edge[v]].capacity - graph[prev_vertex[v]][prev_edge[v]].flow);
            }
            for (int v = sink; v != source; v = prev_vertex[v]) {
                graph[prev_vertex[v]][prev_edge[v]].flow += pushed_flow;
                graph[v][graph[prev_vertex[v]][prev_edge[v]].reverse_index].flow -= pushed_flow;
                cost += pushed_flow * graph[prev_vertex[v]][prev_edge[v]].cost;
            }
            flow += pushed_flow;
        }
        return {flow, cost};
    }

private:
    int n;
    vector<vector<Edge>> graph;
    vector<int> potential, dist, prev_vertex, prev_edge;

    bool bellmanFord(int source, int sink) {
        fill(dist.begin(), dist.end(), INF);
        dist[source] = 0;

        for (int i = 0; i < n - 1; ++i) {
            bool updated = false;
            for (int u = 0; u < n; ++u) {
                for (auto &e : graph[u]) {
                    if (e.capacity > e.flow && dist[u] + e.cost < dist[e.to]) {
                        dist[e.to] = dist[u] + e.cost;
                        prev_vertex[e.to] = u;
                        prev_edge[e.to] = e.reverse_index;
                        updated = true;
                    }
                }
            }
            if (!updated) break;
        }

        return dist[sink] != INF;
    }
};

int main() {
    ifstream infile("cmcm.in");
    ofstream outfile("cmcm.out");

    int N, M, E;
    infile >> N >> M >> E;

    MinCostMaxFlow mcmf(N + M + 2);
    int source = 0, sink = N + M + 1;

    for (int i = 1; i <= N; ++i) {
        mcmf.addEdge(source, i, 1, 0);
    }
    for (int i = 1; i <= M; ++i) {
        mcmf.addEdge(N + i, sink, 1, 0);
    }

    for (int i = 0; i < E; ++i) {
        int P, Q, C;
        infile >> P >> Q >> C;
        mcmf.addEdge(P, N + Q, 1, C);
    }

    pair<int, int> result = mcmf.getMinCostMaxFlow(source, sink);
    outfile << result.first << " " << result.second << endl;

    infile.close();
    outfile.close();

    return 0;
}