Cod sursa(job #3193497)

Utilizator Alexco2003Codarcea Alexandru-Christian Alexco2003 Data 14 ianuarie 2024 18:24:33
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.01 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;



int bfs(int source, int sink, vector<int>& parent,vector<vector<int>>& adjList, vector<vector<int>>& capacity, vector<vector<int>>& flow)
{
    fill(parent.begin(), parent.end(), -1);
    parent[source] = source;

    queue<pair<int, int>> q;
    q.push({source, INT_MAX});

    while (!q.empty())
    {
        int currentNode = q.front().first;
        int currentFlow = q.front().second;
        q.pop();

        for (int neighbor : adjList[currentNode])
        {
            if (parent[neighbor] == -1 && capacity[currentNode][neighbor] > flow[currentNode][neighbor])
            {
                parent[neighbor] = currentNode;
                int newFlow = min(currentFlow, capacity[currentNode][neighbor] - flow[currentNode][neighbor]);
                if (neighbor == sink)
                {
                    return newFlow;
                }
                q.push({neighbor, newFlow});
            }
        }
    }

    return 0;
}

int maxFlow(int n, int source, int sink, vector<vector<int>>& adjList,vector<vector<int>>& capacity, vector<vector<int>>& flow)
{
    vector<int> parent(n * 2 + 2);

    int maxFlow = 0;
    int newFlow;

    while (newFlow = bfs(source, sink, parent, adjList, capacity, flow))
    {
        maxFlow = maxFlow + newFlow;

        int currentNode = sink;
        while (currentNode != source)
        {
            int previousNode = parent[currentNode];
            flow[previousNode][currentNode] = flow[previousNode][currentNode] + newFlow;
            flow[currentNode][previousNode] = flow[currentNode][previousNode] - newFlow;
            currentNode = previousNode;
        }
    }

    return maxFlow;
}


int main()
{

    ifstream f1 ("harta.in");
    ofstream f2 ("harta.out");

    int n;
    f1 >> n;

    int source = 0;
    int sink = n * 2 + 1;

    vector<vector<int>> adjList(n * 2 + 2, vector<int>(n * 2 + 2, 0));
    vector<vector<int>> capacity(n * 2 + 2, vector<int>(n * 2 + 2, 0));
    vector<vector<int>> flow(n * 2 + 2, vector<int>(n * 2 + 2, 0));

    for (int i = 1; i <= n; i++)
    {
        int outDegree, inDegree;
        f1 >> outDegree >> inDegree;

        adjList[source].push_back(i);
        adjList[i].push_back(source);
        capacity[source][i] = outDegree;

        adjList[sink].push_back(i + n);
        adjList[i+n].push_back(sink);
        capacity[i + n][sink] = inDegree;

    }

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

    f2<<maxFlow(n,source,sink,adjList,capacity,flow)<<endl;

    for(int i = 1 ; i <= n ; i++)
        for(int j = n + 1 ; j <= n+n ; j++)
            if(flow[i][j])
                f2<<i<<" "<<j-n<<endl;


    return 0;
}