Cod sursa(job #3190879)

Utilizator LidaraniLida Rani Lidarani Data 8 ianuarie 2024 11:01:22
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.19 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<unordered_map>
#include<queue>
#include<bitset>
#define INF 1e8

std::vector<std::vector<int>> capacitate, flow, adjList;
std::vector<int> parent;
std::vector<bool> visited;
int n, s, t, edges;

void readData()
{
    std::ifstream fin("harta.in");

    fin >> n;

    t = 2 * n + 1;
    s = 0;

    adjList.resize(t + 2, {});
    capacitate.resize(t + 2, std::vector<int>(t + 2));
    flow.resize(t + 2, std::vector<int>(t + 2));
    parent.resize(t + 2);

    for (int i = 1; i <= n; i++)
    {
        int x, y;
        fin >> x >> y;

        edges += x;
        adjList[s].push_back(i);
        adjList[i].push_back(s);
        adjList[n + i].push_back(t);
        adjList[t].push_back(n + i);

        capacitate[s][i] = x;
        capacitate[n + i][t] = y;
    }

    fin.close();

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (i - j)
            {
                adjList[i].push_back(n + j);
                adjList[n + j].push_back(i);
                capacitate[i][n + j] = 1;
            }
}

void afisareMatrice(std::vector<std::vector<int>> matrix)
{
    for(int i = 0; i < matrix.size(); i++)
    {
        std::cout << i << ": ";
        for(int j = 0; j < matrix[i].size(); j++)
            std::cout << matrix[i][j] << ' ';
        std::cout << '\n';
    }   
}

void bfs()
{
    visited.assign(t, false);

    std::queue<int> q;
    q.push(s);

    visited[s] = true;
    parent[s] = 0;

    while (!q.empty())
    {
        int cur = q.front();
        q.pop();

        if (cur == t)
            continue;

        for (int urm : adjList[cur])
        {
            if (!visited[urm] && capacitate[cur][urm] != flow[cur][urm])
            {
                visited[urm] = true;
                parent[urm] = cur;
                q.push(urm);
            }
        }
    }

}

void maxflow(int s, int t)
{
    while (1)
    {
        bfs();

        if (!visited[t])
            break;

        for (auto k : adjList[t])
        {
            if (!visited[k] || capacitate[k][t] == flow[k][t])
                continue;

            parent[t] = k;
            int small = INF, node = t;

            while (node != s)
            {
                small = std::min(small, capacitate[parent[node]][node] - flow[parent[node]][node]);
                node = parent[node];
            }

            if (small)
            {
                node = t;
                while (node != s)
                {
                    flow[parent[node]][node] += small;
                    flow[node][parent[node]] -= small;
                    node = parent[node];
                }
            }

        }
    }
}

void afisareRes()
{
    std::ofstream fout("harta.out");

    fout << edges << '\n';
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n ; j++)
            if (i != j && capacitate[i][n + j] == flow[i][n + j])
                fout << i << ' ' << j << '\n';

    fout.close();
}

int main()
{
    readData();
    //afisareMatrice(adjList);
    maxflow(s, t);
    afisareRes();
}