Cod sursa(job #2961256)

Utilizator lucianul31Moisii Lucian lucianul31 Data 6 ianuarie 2023 01:23:25
Problema Taramul Nicaieri Scor 15
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.25 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <string.h>

using namespace std;

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

const int NMAX = 205;
int Graph[NMAX][NMAX], N, Source, Destination, Father[NMAX], TotalFlow;
bool Seen[NMAX];
vector < int > Edges[NMAX];

bool BFS()
{
    queue < int > Q;
    int X;
    memset(Seen, 0, sizeof(int) * (Destination + 1));
    Seen[0] = 1;
    Q.push(0);
    Father[0] = -1;
    while(!Q.empty())
    {
        X = Q.front();
        Q.pop();
        for(int newX : Edges[X])
        {
            if(!Seen[newX] && Graph[X][newX] != 0)
            {
                Father[newX] = X;
                if(newX == Destination)
                    return 1;
                Q.push(newX);
                Seen[newX] = 1;
            }       
        }
    }
    return 0;
}

void MaxFlow()
{
    int X, Bottleneck;
    while(BFS())
    {
        X = Father[Destination];
        Bottleneck = Graph[X][Destination];
        while(Father[X] != -1)
        {
            Bottleneck = min(Bottleneck, Graph[Father[X]][X]);
            X = Father[X];
        }
        TotalFlow += Bottleneck;
        X = Destination;
        while(Father[X] != -1)
        {
            Graph[Father[X]][X] -= Bottleneck;
            Graph[X][Father[X]] += Bottleneck;
            X = Father[X];
        }
    }
}

void PrintEdges()
{
    for(int i = 1; i <= N; i++)
        for(int j = N + 1; j < Destination; j++)
            if(Graph[j][i])
                out << i << ' ' << j - N << '\n';
}

int main()
{
    int inDegree, outDegree;
    in >> N;
    Destination = 2 * N + 1;
    for(int i = 1; i <= N; i++)
    {
        in >> outDegree >> inDegree;
        Graph[0][i] = outDegree;
        Graph[i + N][Destination] = inDegree;
        Edges[0].push_back(i);
        Edges[i].push_back(0);
        Edges[i + N].push_back(Destination);
        Edges[Destination].push_back(i + N);
    }
    for(int i = 1; i <= N; i++)
        for(int j = N + 1; j < Destination; j++)
            if(i != j - N)
                Graph[i][j] = 1, Edges[i].push_back(j), Edges[j].push_back(i);
    MaxFlow();
    out << TotalFlow << '\n';
    PrintEdges();
}