Cod sursa(job #3189961)

Utilizator FlaviaF7Fota Stefania-Flavia FlaviaF7 Data 6 ianuarie 2024 18:18:05
Problema Taramul Nicaieri Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.83 kb
#include <bits/stdc++.h>
using namespace std;

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

// initializam un flux null si o matrice de capacitati
int cap[101][101], flux[101][101];

// initializam un vector de parinti
vector<int> parent;

// initializam o matrice de adiacenta
vector<int> mat[101];

// numarul de orase
int n;

// bfs pentru a gasi un drum de crestere (un lant de la sursa la destinatie)
// capacele muchiilor trebuie sa fie strict pozitive, si mai mari decat fluxul curent
int bfs(int start, int last) {

    // initializam o coada si un vector de vizitati
    deque<int> q;
    vector<bool> visited(last + 1, false);

    // initializam vectorul de parinti
    parent.assign(last + 1, 0);

    q.push_back(start);
    visited[start] = true;

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

        // daca am ajuns la destinatie, iesim din bfs
        if (nod == last) break;

        // parcurgem vecinii nodului curent
        for (int i = 0; i < mat[nod].size(); i++) {
            int vecin = mat[nod][i];

            // daca capacitatea muchiei este mai mare decat fluxul curent
            // adaugam nodul in coada
            if (!visited[vecin] && cap[nod][vecin] > flux[nod][vecin]) {
                q.push_back(vecin);

                // tinem nodul anterior in vectorul de parinti
                // pentru a reconstrui drumul de crestere ulterior
                parent[vecin] = nod;
                visited[vecin] = true;
            }
        }
    }

    // daca am ajuns la destinatie(am gasit un drum de crestere), returnam 1
    // altfel, returnam 0
    if (parent[last]) return 1;
    return 0;
}

// algoritmul lui Edmonds-Karp - determinam fluxul maxim
int edmonds_karp(int start, int last) {
    int flow = 0;
    int i, mini;

    // cat timp exista un drum de crestere (aflate cu bfs)
    while (bfs(start, last)) {
        mini = INT_MAX;
        i = last;

        // determinam fluxul minim pe drumul de crestere,
        // comparand fluxul dintre nodul curent si parintele sau cu fluxul minim curent
        while (i != 0) {
            if ((cap[parent[i]][i] - flux[parent[i]][i]) < mini)
                mini = (cap[parent[i]][i] - flux[parent[i]][i]);

            i = parent[i];
        }

        i = last;
        
        // actualizam fluxurile pe drum
        while (i != 0) {
            // fluxul creste pe muchiile directe si scade pe cele inverse
            flux[parent[i]][i] += mini;
            flux[i][parent[i]] -= mini;

            i = parent[i];
        }

        // adaugam fluxul minim la fluxul total
        flow += mini;
    }

    return flow;
}

int main() {
    int start, last, x, y;
    
    fin >> n;
    
    start = 0;
    last = n + n + 1;
    
    // initializam matricea de adiacenta si matricea de capacitati
    for (int i = 1; i <= n; i++) {
        fin >> x >> y;

        int j = n + i;
        
        mat[start].push_back(i);
        mat[j].push_back(last);
    
        cap[start][i] = x;
        cap[j][last] = y;
    }

    // adaugam muchii intre orase cu restricitiile: 
    // 1. nu putem merge din oras in el insusi
    // 2. nu putem avea muchia i-j daca avem deja muchia j-i
    for (int i = 1; i <= n; i++) {
        for (int j = n + 1; j <= n + n; j++) {
            if ((i % n) != (j % n)) {
                mat[i].push_back(j);
                mat[j].push_back(i);
                cap[i][j] = 1;
            }
        }
    }

    // afisam fluxul maxim
    fout << edmonds_karp(start, last) << endl;
    
    // afisam drumurile
    for (int i = 1; i <= n; i++) {
        for (int j = n + 1; j <= n + n; j++) {
            if (flux[i][j] == 1)
                fout << i << ' ' << j - n << endl;
        }
    }
    return 0;
}