Cod sursa(job #3041420)

Utilizator SerbanCaroleSerban Carole SerbanCarole Data 31 martie 2023 14:46:14
Problema Cuplaj maxim de cost minim Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.92 kb
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

//ifstream cin("cmcm.in");
//ofstream cout("cmcm.out");

const int MAX = 610;
const int inf = 1e9 + 1;
int cap[MAX][MAX] , flow[MAX][MAX] , n , m , x , y , e , cost[MAX][MAX] , c, sink ,source;
int dist[MAX] , pre[MAX];
bool in_q[MAX];
vector <int> g[MAX];

bool bf(){

    queue<int>q;
    q.push(source);

    for(int i = source ; i <= sink ; i++){

        dist[i] = inf;
        pre[i] = 0;
        in_q[i] = 0;
    }

    in_q[source] = 1;
    dist[source] = 0;

    while(!q.empty()){

        x = q.front();
        q.pop();
        in_q[x] = 0;

        for(auto it : g[x]){

            if(cap[x][it] - flow[x][it] > 0 && dist[it] > dist[x] + cost[x][it]){

                dist[it] = dist[x] + cost[x][it];
                pre[it] = x;

                if(!in_q[it]){

                    in_q[it] = 1;

                    q.push(it);
                }
            }
        }
    }

    return (dist[sink]!=inf);
}

int main()
{

    cin >> n >> m >> e;

    while(e--){

        cin >> x >> y >> c;
        y += n;

        cost[x][y] = c;
        cost[y][x] = -c;
        cap[x][y] = 1;

        g[x].push_back(y);
        g[y].push_back(x);
    }

    for(int i = 1 ; i <= n ; i++){

        cap[0][i] = 1;

        g[0].push_back(i);
        g[i].push_back(0);
    }

    sink = m+n+1;
    source = 0;

    for(int j = 1 ; j <= m ; j++){

        int i = j + n;

        cap[i][sink] = 1;

        g[sink].push_back(i);
        g[i].push_back(sink);
    }

    int nr = 0 , k = 0;

    while(bf()){

        nr++;
        k+=dist[sink];

        int aux = sink;

        while(pre[aux]){

            flow[pre[aux]][aux]++;
            flow[aux][pre[aux]]--;

            aux = pre[aux];
        }
    }

    cout << nr << ' ' << k << '\n';

    return 0;
}