Cod sursa(job #2961995)

Utilizator lucianul31Moisii Lucian lucianul31 Data 7 ianuarie 2023 16:25:24
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.52 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, Flow = 0, Bottleneck;
    memset(Seen, 0, (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)
            {
                Father[newX] = X;
                Q.push(newX);
                Seen[newX] = 1;
            }
        }
    }
    for (int Node : Edges[Destination])
        if (Seen[Node] && Graph[Node][Destination] > 0)
        {
            Father[Destination] = Node;
            X = Node;
            Bottleneck = Graph[X][Destination];
            while (Father[X] != -1)
            {
                Bottleneck = min(Bottleneck, Graph[Father[X]][X]);
                X = Father[X];
            }
            Flow += Bottleneck;
            X = Destination;
            while (Father[X] != -1)
            {
                Graph[Father[X]][X] -= Bottleneck;
                Graph[X][Father[X]] += Bottleneck;
                X = Father[X];
            }
        }
    return Flow;
}

void PrintEdges()
{
    vector < pair < int, int > > Solution;
    for (int i = 1; i <= N; i++)
        for (int j = N + 1; j < Destination; j++)
            if (Graph[j][i])
                Solution.push_back({i, j - N});
    out << Solution.size() << '\n';
    for(pair < int, int > &it : Solution)
        out << it.first << ' ' << it.second << '\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);
    while (BFS());
    PrintEdges();
}