Cod sursa(job #2960484)

Utilizator pasare.franci@yahoo.comPasare Francisca [email protected] Data 4 ianuarie 2023 14:55:09
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I, Semestrul 2 Marime 2.12 kb
#include <bits/stdc++.h>
#define inf INT_MAX
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
int tata[220], v[220][220], in[220], out[220], n, nod, flow, max_flow;
bool vizitat[220];
bool bfs() {
    queue<int> q;
    memset(tata, 0, sizeof(tata));
    memset(vizitat, false, sizeof(vizitat));

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

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


        for (int i = 1; i <= 2 * n + 1; i++) {
            if (!vizitat[i] && v[front][i] > 0) {
                q.push(i);
                vizitat[i] = true;
                tata[i] = front;
            }
        }
    }
    return false;
}

void reglare_Flow() {
    while (bfs()) {
        for (int i = 1; i <= n; i++) {
            //daca a fost vizitat si daca a ajuns la destinatie
            if (vizitat[n + i] && v[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, v[tata[nod]][nod]);
                if (flow == 0)
                    continue;
                //reglam flow-ul
                for (nod = 2 * n + 1; nod != 0; nod = tata[nod]) {
                    v[tata[nod]][nod] -= flow;
                    v[nod][tata[nod]] += flow;
                }
                //adaugam iP ul la flow ul total
                max_flow += flow;
            }
        }
    }
}

int main() {
    f >> n;
    for (int i = 1; i <= n; i++) {
        f >> out[i] >> in[i];
        v[0][i] = out[i];
        v[n + i][2 * n + 1] = in[i];

        for (int j = 1; j <= n; j++)
            if (i != j)
                v[i][n + j] = 1;
    }

    reglare_Flow();

    g <<max_flow<< '\n';
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            if (v[i][n + j] == 0 && i != j)
                g << i << " " << j << '\n';
    }

    return 0;
}