Cod sursa(job #2959992)

Utilizator ctimburCristina T ctimbur Data 3 ianuarie 2023 13:23:23
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.4 kb
#include <algorithm>
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>

using namespace std;

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

int n, m, x, y, capacitate, mat[1001][1001];
queue <int> q;
bool visited[1001];
int parinte[1001];

bool bfs() {
    while (!q.empty())
        q.pop();

    for (int i = 0; i <= 2 * n + 1; ++i) {
        parinte[i] = -1;
        visited[i] = false;
    }
    q.push(0);
    visited[0] = true;

    while (!q.empty()) {
        int nod = q.front();
        q.pop();

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

        for (int i = 1; i <= 2 * n + 1; ++i)
            if (visited[i] == false && mat[nod][i] > 0) {
                q.push(i);
                visited[i] = true;
                parinte[i] = nod;
            }
    }

    return false;
}

int fluxMax() {
    int maxFlow = 0;
    while (bfs()) {
        for (int i = n + 1; i < 2 * n + 1; i++) {
            if (mat[i][2 * n + 1] > 0 && visited[i] == true) {
                int frunza = i;

                vector <int> drum;
                drum.push_back(2 * n + 1);
                drum.push_back(frunza);

                int nod = parinte[frunza];

                if (nod == 0)
                    drum.push_back(nod);
                else {
                    while (nod != 0) {
                        drum.push_back(nod);
                        nod = parinte[nod];
                    }
                    drum.push_back(0);
                }
                reverse(drum.begin(), drum.end());
                int minCap = 2e9;
                for (int i = 0; i < drum.size() - 1; i++)
                    minCap = min(minCap, mat[drum[i]][drum[i+1]]);
                maxFlow += minCap;
                for (int i = 0; i < drum.size() - 1; i++) {
                    mat[drum[i]][drum[i + 1]] -= minCap;
                    mat[drum[i + 1]][drum[i]] += minCap;
                }
            }
        }
    }
    return maxFlow;
}

int main() {
    fin >> n;
    for (int i = 1; i <= n; i++) {
        fin >> x >> y;
        mat[0][i] = x;
        mat[n + i][2 * n + 1] = y;
        for (int nod = 1; nod <= n; nod++)
            if (nod != i)
                mat[i][n + nod] = 1;
    }

    fout << fluxMax() << endl;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (mat[i][n + j] == 0 && i != j)
                fout << i << " " << j << endl;
    return 0;
}