Cod sursa(job #2961728)

Utilizator popescumateicalinPopescu Matei Calin popescumateicalin Data 6 ianuarie 2023 21:46:57
Problema Taramul Nicaieri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.23 kb
#include <fstream>
#include <vector>
#include <queue>

std::ifstream in("harta.in");
std::ofstream out("harta.out");

const int N = 205, MAX = 1e+7;
int n, maxFlow, grid[N][N];
std::vector<int> vis(N), repr(N);

bool BFS()
{
    std::fill(repr.begin(), repr.end(), -1);
    std::fill(vis.begin(), vis.end(), 0);

    std::queue<int> Q;
    Q.push(0);
    vis[0] = 1;

    while (!Q.empty())
    {
        int x = Q.front();
        Q.pop();

        if (x == 2 * n + 1)
            return true;

        for (int v = 1; v <= 2 * n + 1; v++)
        {
            if (!grid[x][v] || vis[v])
                continue;
            Q.push(v);
            vis[v] = 1;
            repr[v] = x;
        }
    }
    return false;
}

int main()
{
    in >> n;
    for (int i = 1; i <= n; i++)
    {
        int x, y;
        in >> x >> y;
        grid[0][i] = x;
        grid[n + i][2 * n + 1] = y;

        for (int j = 1; j <= n; j++)
            if (i != j)
                grid[i][n + j] = 1;
    }

    /*for (int i = 0; i <= 2 * n + 1; i++)
    {
        for (int j = 0; j <= 2 * n + 1; j++)
            out << grid[i][j] << ' ';
        out << '\n';
    }*/

    out << '\n';
    while (BFS())
    {
        for (int x = n + 1; x < 2 * n + 1; x++)
        {
            if (!grid[x][2 * n + 1] || !vis[x])
                continue;

            std::vector<int> path;
            path.push_back(x);
            int curr = repr[x];

            while (curr != 0)
            {
                path.push_back(curr);
                curr = repr[curr];
            }
            path.push_back(0);

            int flow = MAX;
            for (int i = path.size() - 1; i >= 1; i--)
                flow = std::min(flow, grid[path[i]][path[i - 1]]);
            maxFlow += flow;

            for (int i = path.size() - 1; i >= 1; i--)
            {
                grid[path[i]][path[i - 1]] -= flow;
                grid[path[i - 1]][path[i]] += flow;
            }
        }
    }

    out << maxFlow << '\n';
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (i != j && grid[i][n + j] == 0)
                out << i << " " << j << '\n';

    return 0;
}