Cod sursa(job #2962369)

Utilizator Marius_TillingerTillinger Marius Marius_Tillinger Data 8 ianuarie 2023 14:23:23
Problema Taramul Nicaieri Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector> 
#include <queue>

using namespace std;

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

int parent[202], capacity[202][202], n, m, nod, flow, maxFlow, i, j;
int currentNode;
bool visited[202];
queue<int> q;

bool bfs() {

    memset(parent, 0, sizeof(parent));
    memset(visited, false, sizeof(visited));

    q.push(0);
    visited[0] = true;
    parent[0] = -1;

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

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

        for (i=1; i<=2*n+1; i++) {
            if (!visited[i] && capacity[currentNode][i] > 0) {
                q.push(i);
                visited[i] = true;
                parent[i] = currentNode;
            }
        }
    }
    return false;
}

void edmondskarp() {
    while (bfs()) {
        for (i=1; i<=n; i++) {
            if (visited[n+i] && capacity[n+i][2*n+1] > 0) {
                flow = 1000000;
                parent[2*n+1] = n+i;

                for (nod=2*n+1; nod!=0; nod=parent[nod])
                    flow = min(flow, capacity[parent[nod]][nod]);
                if (flow == 0)
                    continue;

                for (nod=2*n+1; nod!=0; nod=parent[nod]) {
                    capacity[parent[nod]][nod] -= flow;
                    capacity[nod][parent[nod]] += flow;
                }

                maxFlow += flow;
            }
        }
    }
}

int main() {

    fin >> n;

    int x, y;

    for (i=1; i<=n; i++) {
        fin >> x >> y;
        capacity[0][i] = x;
        capacity[n+i][2*n+1] = y;

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

    edmondskarp();

    fout << maxFlow << '\n';
    for (i=1; i<=n; i++) {
        for (j=1; j<=n; j++)
            if (capacity[i][n + j] == 0 && i!=j)
                fout << i << " " << j << '\n';
    }

    return 0;
}