Cod sursa(job #2297730)

Utilizator Tataru_AdelinTataru Adelin Tataru_Adelin Data 6 decembrie 2018 13:44:45
Problema Cuplaj maxim de cost minim Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4.87 kb
#include <bits/stdc++.h>

using namespace std;

class Unit
{
public:
    int cap;
    int cost;

public:
    void initialize(int x, int y)
    {
        cap = x;
        cost = y;
    }

    Unit()
    {}

    Unit(int x, int y)
    {
        initialize(x, y);
    }
};

class Node
{
public:
    int node;
    int cost;

public:
    void initialize(int x, int y)
    {
        node = x;
        cost = y;
    }

    Node()
    {}

    Node(int x, int y)
    {
        initialize(x, y);
    }
};

class Comp
{
public:
    bool operator() (Node a, Node b)
    {
        return a.cost > b.cost;
    }
};

const int INF = numeric_limits<int>::max();

void reset(vector <int> &v)
{
    for(unsigned i = 0; i < v.size(); i++)
        v[i] = 0;
}

void bellman(int start, int dest, vector <int> &dist, vector <vector <int>> &path, vector <vector <Unit>> &flux)
{
    queue <int> q;
    vector <bool> in_q(path.size(), false);

    dist[start] = 0;
    q.push(start);
    in_q[start] = true;

    int current, vec;

    while(!q.empty())
    {
        current = q.front();
        q.pop();
        in_q[current] = false;

        for(unsigned i = 0; i < path[current].size(); i++)
        {
            vec = path[current][i];
            if(dist[vec] > dist[current] + flux[current][vec].cost && flux[current][vec].cap > 0)
            {
                dist[vec] = dist[current] + flux[current][vec].cost;

                if(!in_q[vec])
                {
                    q.push(vec);
                    in_q[vec] = true;
                }
            }
        }
    }
}

bool dijkstra(int start, int dest, vector <int> &parent, vector <int> &dist, vector <vector <int>> &path, vector <vector <Unit>> &flux)
{
    priority_queue <Node, vector <Node>, Comp> q;
    vector <bool> viz(path.size(), false);

    reset(parent);

    vector <int> dist_d(dist.size(), INF);
    vector <int> dist_u(dist.size());

    q.push(Node(start, 0));
    dist_d[start] = 0;

    Node current, vec;

    while(!q.empty())
    {
        current = q.top();
        q.pop();

        if(!viz[current.node])
        for(unsigned i = 0; i < path[current.node].size(); i++)
        {
            vec.node = path[current.node][i];
            if(dist_d[vec.node] > current.cost + flux[current.node][vec.node].cost + dist[current.node] - dist[vec.node] && flux[current.node][vec.node].cap > 0)
            {
                dist_d[vec.node] = current.cost + flux[current.node][vec.node].cost + dist[current.node] - dist[vec.node];
                dist_u[vec.node] = dist_u[current.node] + flux[current.node][vec.node].cost;

                parent[vec.node] = current.node;

                q.push(Node(vec.node, dist_d[vec.node]));
            }
        }

        viz[current.node] = true;
    }

    for(unsigned i = 0; i < dist.size(); i++)
        dist[i] = dist_u[i];

    for(unsigned i = 0; i < dist.size(); i++)
        cout<<dist[i]<<' ';
    cout<<"\n\n";

    if(dist_d[dest] != INF)
        return true;
    else
        return false;
}

void update(int start, int dest, int &max_flux, int &min_cost, vector <int> &parent, vector <int> &dist, vector <vector <int>> &path, vector <vector <Unit>> &flux)
{
    int current;
    int min_flux = INF;

    for(current = dest; current != start; current = parent[current])
    {
        min_flux = min(min_flux, flux[parent[current]][current].cap);
    }

    for(current = dest; current != start; current = parent[current])
    {
        flux[parent[current]][current].cap -= min_flux;
        flux[current][parent[current]].cap += min_flux;
    }

    max_flux += min_flux;
    min_cost += min_flux * dist[dest];
}

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

int main()
{
    int left, right, edges;
    fin>>left>>right>>edges;

    vector <vector <int>> path(left + right + 3);
    vector <vector <Unit>> flux(left + right + 3, vector <Unit> (left + right + 3, Unit(0, 0)));
    vector <int> dist(left + right + 3, INF);
    vector <int> parent(left + right +3);


    int x, y, c;
    for(; edges; edges--)
    {
        fin>>x>>y>>c;

        path[x].push_back(y + left);
        flux[x][y + left] = Unit(1, c);
        path[y + left].push_back(x);
        flux[y + left][x] = Unit(0, -c);
    }

    int start = left + right + 1;
    int dest = left + right + 2;

    for(int i = 1; i <= left; i++)
    {
        path[start].push_back(i);
        flux[start][i] = Unit(1, 0);
        path[i].push_back(start);
        flux[i][start] = Unit(0, 0);
    }

    for(int i = left + 1; i <= left + right; i++)
    {
        path[i].push_back(dest);
        flux[i][dest] = Unit(1, 0);
        path[dest].push_back(i);
        flux[dest][i] = Unit(0, 0);
    }

    bellman(start, dest, dist, path, flux);

    int min_cost = 0, max_flux = 0;

    while(dijkstra(start, dest, parent, dist, path, flux))
    {
        update(start, dest, max_flux, min_cost, parent, dist, path, flux);
    }

    fout<<max_flux<<' '<<min_cost<<'\n';

    return 0;
}