Cod sursa(job #3179619)

Utilizator Razvan48Capatina Razvan Nicolae Razvan48 Data 3 decembrie 2023 22:39:42
Problema Cc Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.92 kb
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

const int NMAX = 100;

vector<int> graf[1 + 2 * NMAX + 1];
int capacitate[1 + 2 * NMAX + 1][1 + 2 * NMAX + 1];
int cost[1 + 2 * NMAX + 1][1 + 2 * NMAX + 1];

queue<int> q;
bool inCoada[1 + 2 * NMAX + 1];

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

int distInitial[1 + 2 * NMAX + 1];
int distDijkstra[1 + 2 * NMAX + 1];
int distReala[1 + 2 * NMAX + 1];

int tata[1 + 2 * NMAX + 1];

void bellmanFord(int n)
{
    for (int i = 0; i <= 2 * n + 1; ++i)
        distInitial[i] = 1e9;

    distInitial[0] = 0;
    q.emplace(0);
    inCoada[0] = true;

    while (!q.empty())
    {
        int nod = q.front();
        q.pop();
        inCoada[nod] = false;

        for (int i = 0; i < graf[nod].size(); ++i)
        {
            int vecin = graf[nod][i];

            if (capacitate[nod][vecin] > 0 && distInitial[nod] + cost[nod][vecin] < distInitial[vecin])
            {
                distInitial[vecin] = distInitial[nod] + cost[nod][vecin];

                if (!inCoada[vecin] && vecin != 2 * n + 1)
                {
                    q.emplace(vecin);
                    inCoada[vecin] = true;
                }
            }
        }
    }
}

bool dijkstra(int n)
{
    for (int i = 0; i <= 2 * n + 1; ++i)
        tata[i] = -1;

    for (int i = 0; i <= 2 * n + 1; ++i)
        distDijkstra[i] = 1e9;

    distDijkstra[0] = 0;
    distReala[0] = 0;
    tata[0] = 0;
    pq.emplace(0, 0);

    while (!pq.empty())
    {
        int nod = pq.top().second;
        int distNod = pq.top().first;
        pq.pop();

        if (distNod > distDijkstra[nod])
            continue;

        for (int i = 0; i < graf[nod].size(); ++i)
        {
            int vecin = graf[nod][i];

            if (capacitate[nod][vecin] > 0 &&
                distNod + distInitial[nod] + cost[nod][vecin] - distInitial[vecin] < distDijkstra[vecin])
            {
                distDijkstra[vecin] = distNod + distInitial[nod] + cost[nod][vecin] - distInitial[vecin];
                distReala[vecin] = distReala[nod] + cost[nod][vecin];
                tata[vecin] = nod;

                if (vecin != 2 * n + 1)
                    pq.emplace(distDijkstra[vecin], vecin);
            }
        }
    }

    for (int i = 0; i <= 2 * n + 1; ++i)
        distInitial[i] = distReala[i];

    return distDijkstra[2 * n + 1] < 1e9;
}

int main()
{
    ifstream in("cc.in");
    ofstream out("cc.out");

    ios_base::sync_with_stdio(false);
    in.tie(nullptr);
    out.tie(nullptr);

    int n;
    in >> n;

    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            in >> cost[i][n + j];
            cost[n + j][i] = -cost[i][n + j];
            graf[i].emplace_back(n + j);
            graf[n + j].emplace_back(i);
            capacitate[i][n + j] = 1;
        }
    }

    for (int i = 1; i <= n; ++i)
    {
        graf[0].emplace_back(i);
        graf[i].emplace_back(0);
        capacitate[0][i] = 1;
    }

    for (int i = n + 1; i <= 2 * n; ++i)
    {
        graf[i].emplace_back(2 * n + 1);
        graf[2 * n + 1].emplace_back(i);
        capacitate[i][2 * n + 1] = 1;
    }

    bellmanFord(n);

    int sol = 0;

    while (dijkstra(n))
    {
        int capMinima = 1e9;
        for (int nodCrt = 2 * n + 1; nodCrt != tata[nodCrt]; nodCrt = tata[nodCrt])
            capMinima = min(capMinima, capacitate[tata[nodCrt]][nodCrt]);
        for (int nodCrt = 2 * n + 1; nodCrt != tata[nodCrt]; nodCrt = tata[nodCrt])
        {
            capacitate[tata[nodCrt]][nodCrt] -= capMinima;
            capacitate[nodCrt][tata[nodCrt]] += capMinima;
        }

        sol += distReala[2 * n + 1] * capMinima;
    }

    out << sol << '\n';

    in.close();
    out.close();

    return 0;
}