Cod sursa(job #2956833)

Utilizator dragosteleagaDragos Teleaga dragosteleaga Data 20 decembrie 2022 19:29:48
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.4 kb
#include <bits/stdc++.h>
#define dim 220
#define inf INT_MAX
using namespace std;
ifstream f("harta.in");
ofstream o("harta.out");
int tata[dim], a[dim][dim], in[dim], out[dim], n, m, nod, flow, maxFlow;
bool viz[dim];
//algoritmul clasic de bfs pt max flow doar ca in loc de t am 2n+1
bool bfs() {
    queue<int> coada;
    memset(tata, 0, sizeof(tata));
    memset(viz, false, sizeof(viz));

    coada.push(0);
    viz[0] = true;
    tata[0] = -1;
    while (!coada.empty()) {
        int front = coada.front();
        coada.pop();

        if (front == 2 * n + 1)
            return true;


        for (int i = 1; i <= 2 * n + 1; i++) {
            if (!viz[i] && a[front][i] > 0) {
                coada.push(i);
                viz[i] = true;
                tata[i] = front;
            }
        }
    }
    return false;
}
void citireDate() {
    f >> n;
    for (int i = 1; i <= n; i++) {
        f >> out[i] >> in[i];
        //Adaugam un nou start si un nou final(cu muchii de
        // capacitati egale cu gradele out, respectiv in),
        //si dublam nodurile, ca sa l putem lega pe fiecare cu fiecare
        //2n+1 fiind t-ul
        a[0][i] = out[i];
        a[n + i][2 * n + 1] = in[i];

        for (int j = 1; j <= n; j++)
            if (i != j)
                a[i][n + j] = 1;
    }
}
void reglamFlow() {
    while (bfs()) {
        for (int i = 1; i <= n; i++) {
            //daca a fost vizitat si daca a ajuns la destinatie
            if (viz[n + i] && a[n + i][2 * n + 1] > 0) {
                flow = inf;
                tata[2 * n + 1] = n + i;
                //parcurgem lantul de la T la S si luam minimul(iP)
                for (nod = 2 * n + 1; nod != 0; nod = tata[nod])
                    flow = min(flow, a[tata[nod]][nod]);
                if (flow == 0)
                    continue;
                //reglam flow-ul
                for (nod = 2 * n + 1; nod != 0; nod = tata[nod]) {
                    a[tata[nod]][nod] -= flow;
                    a[nod][tata[nod]] += flow;
                }
                //adaugam iP ul la flow ul total
                maxFlow += flow;
            }
        }
    }
}
void afisareDate() {
    o << maxFlow << '\n';
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            if (a[i][n + j] == 0 && i != j)
                o << i << " " << j << '\n';
    }
}
int main() {
    citireDate();
    reglamFlow();
    afisareDate();

    return 0;
}