Cod sursa(job #2960826)

Utilizator Marius_TillingerTillinger Marius Marius_Tillinger Data 4 ianuarie 2023 23:57:43
Problema Taramul Nicaieri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.33 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>

using namespace std;

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

int n, source, sink, flow, maxflow, element;

vector<bool> visited;
vector<int> parent;
vector<vector<int>> capacity;
queue<int> q;

bool bfs() {

    fill(visited.begin(), visited.end(), 0);
    fill(parent.begin(), parent.end(), 0);

    visited[0] = 1;
    parent[0] = -1;

    q.push(0);

    while (!q.empty()) {

        int currentNode = q.front();
        q.pop();

        if (currentNode == sink) {
            return 1;
        }

        for (int i=1; i<=sink; i++) {
            if (!visited[i] && capacity[currentNode][i] > 0) {
                q.push(i);
                visited[i] = 1;
                parent[i] = currentNode;
            }
        }
    }

    return 0;
}

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

                for (element = sink; element!=0; element = parent[element]) 
                    flow = min (flow, capacity[parent[element]][element]);
                
                if (flow == 0) continue;

                for (element = sink; element!=0; element = parent[element]) {
                    capacity[element][parent[element]] += flow;
                    capacity[parent[element]][element] -= flow;
                }

                maxflow += flow;
            }
        }
    }
}

int main () {

    fin >> n;

    source = 0;
    sink = 2*n + 1;

    visited.resize(2*n+2,0);
    parent.resize(2*n+2, 0);
    capacity.resize(2*n+2, vector<int>(2*n+2, 0));

    for (int i=1; i<=n; i++) {

       int x,y;
       fin >> x >> y;

       capacity[source][i] = x;
       capacity[i+n][sink] = y;

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

    edmondskarp();

    fout << maxflow << "\n";

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

    return 0;
}