Cod sursa(job #3233280)

Utilizator MirceaDonciuLicentaLicenta Mircea Donciu MirceaDonciuLicenta Data 2 iunie 2024 21:21:23
Problema Cuplaj maxim de cost minim Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.2 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 to, capacity, cost, flow, rev;
};

class MinCostMaxFlow {
public:
    MinCostMaxFlow(int n) : n(n), graph(n), potential(n, 0), dist(n), prevVertex(n), prevEdge(n), inQueue(n) {}

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

    pair<int, int> getMinCostMaxFlow(int source, int sink) {
        int flow = 0, cost = 0;
        while (shortestPath(source, sink)) {
            int f = INF;
            for (int v = sink; v != source; v = prevVertex[v]) {
                f = min(f, graph[prevVertex[v]][prevEdge[v]].capacity - graph[prevVertex[v]][prevEdge[v]].flow);
            }
            for (int v = sink; v != source; v = prevVertex[v]) {
                Edge &e = graph[prevVertex[v]][prevEdge[v]];
                e.flow += f;
                graph[v][e.rev].flow -= f;
                cost += f * e.cost;
            }
            flow += f;
        }
        return {flow, cost};
    }

private:
    int n;
    vector<vector<Edge>> graph;
    vector<int> potential, dist, prevVertex, prevEdge, inQueue;

    bool shortestPath(int source, int sink) {
        fill(dist.begin(), dist.end(), INF);
        fill(inQueue.begin(), inQueue.end(), 0);
        dist[source] = 0;
        queue<int> q;
        q.push(source);
        inQueue[source] = 1;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            inQueue[u] = 0;
            for (int i = 0; i < graph[u].size(); ++i) {
                Edge &e = graph[u][i];
                if (e.flow < e.capacity && dist[u] + e.cost + potential[u] - potential[e.to] < dist[e.to]) {
                    dist[e.to] = dist[u] + e.cost + potential[u] - potential[e.to];
                    prevVertex[e.to] = u;
                    prevEdge[e.to] = i;
                    if (!inQueue[e.to]) {
                        q.push(e.to);
                        inQueue[e.to] = 1;
                    }
                }
            }
        }
        if (dist[sink] == INF) return false;
        for (int i = 0; i < n; ++i) {
            if (dist[i] < INF) potential[i] += dist[i];
        }
        return true;
    }
};

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;
}