Cod sursa(job #2961154)

Utilizator lucianul31Moisii Lucian lucianul31 Data 5 ianuarie 2023 22:16:05
Problema Taramul Nicaieri Scor 15
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.46 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];
queue < int > Q;
vector < int > Edges[NMAX];

int BFS()
{
    int Flow = 0, Bottleneck, 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(newX == Destination)
                continue;
            if(!Seen[newX] && Graph[X][newX] > 0)
                Q.push(newX), Seen[newX] = 1, Father[newX] = X;
        }
    }
    for(int Node : Edges[Destination])
    {
        if(!Seen[Node])
            continue;
        X = Node;
        Bottleneck = Graph[X][Destination];
        while(Father[X] != -1)
        {
            Bottleneck = min(Bottleneck, Graph[Father[X]][X]);
            X = Father[X];
        }
        Flow += Bottleneck;
        X = Node;
        Graph[X][Destination] -= Bottleneck;
        Graph[Destination][X] += Bottleneck;
        while(Father[X] != -1)
        {
            Graph[Father[X]][X] -= Bottleneck;
            Graph[X][Father[X]] += Bottleneck;
            X = Father[X];
        }
    }
    return Flow;
}

void MaxFlow()
{
    int flow = BFS();
    while(flow)
    {
        TotalFlow += flow;
        flow = BFS();
    }
}

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

int main()
{
    int inDegree, outDegree;
    in >> N;
    Destination = N + 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)
                continue;
            else
                Graph[i][j] = 1, Edges[i].push_back(j), Edges[j].push_back(i);
    MaxFlow();
    out << TotalFlow << '\n';
    PrintEdges();
}