Cod sursa(job #2962357)

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

using namespace std;

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

int n, flow, maxflow, element;
int capacity[202][202];

queue<int> q;

int parent[202];
bool visited[202];

bool bfs() {

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

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

    q.push(0);

    while (!q.empty()) {

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

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

        for (int 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 (int 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 (int element = 2*n+1; element!=0; element = parent[element]) 
                    flow = min (flow, capacity[parent[element]][element]);
                
                if (flow == 0) continue;

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

                maxflow += flow;
            }
        }
    }
}

int main () {

    fin >> n;

    // scopul acestui mod de executie al algoritmului este crearea artificiala
    // a unui nou start si un nou final, dupa care dublam nodurile si 
    // putem sa le legam, startul cu multimea 1 si finalul cu multimea 2
    for (int i=1; i<=n; i++) {

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

       capacity[0][i] = x;
       capacity[i+n][2*n+1] = 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;
}