Cod sursa(job #3190034)

Utilizator victorstefan28Cucu Victor Stefan victorstefan28 Data 6 ianuarie 2024 20:32:34
Problema Taramul Nicaieri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.31 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

const int MAXN = 205; // Numărul maxim de noduri (N orașe + N intermediare + sursă + destinație)
const int INF = 1e9;  // Valoarea infinitului pentru acest context

int N, capacitate[MAXN][MAXN], flux[MAXN][MAXN], parinte[MAXN];
vector<int> graf[MAXN];

bool bfs(int s, int t) {
    memset(parinte, -1, sizeof(parinte));
    queue<int> q;
    q.push(s);
    parinte[s] = -2;

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

        for (int vecin : graf[nod]) {
            if (parinte[vecin] == -1 && capacitate[nod][vecin] - flux[nod][vecin] > 0) {
                parinte[vecin] = nod;
                if (vecin == t) {
                    return true;
                }
                q.push(vecin);
            }
        }
    }

    return false;
}

int fordFulkerson(int s, int t) {
    int flux_maxim = 0;

    while (bfs(s, t)) {
        int flux_curent = INF;
        for (int nod = t; nod != s; nod = parinte[nod]) {
            int prev = parinte[nod];
            flux_curent = min(flux_curent, capacitate[prev][nod] - flux[prev][nod]);
        }

        for (int nod = t; nod != s; nod = parinte[nod]) {
            int prev = parinte[nod];
            flux[prev][nod] += flux_curent;
            flux[nod][prev] -= flux_curent;
        }

        flux_maxim += flux_curent;
    }

    return flux_maxim;
}

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

    fin >> N;
    int s = 0, t = 2 * N + 1; // Sursa și destinația în graf

    for (int i = 1, a, b; i <= N; ++i) {
        fin >> a >> b;
        graf[s].push_back(i);
        graf[i].push_back(s);
        capacitate[s][i] = a;

        graf[i + N].push_back(t);
        graf[t].push_back(i + N);
        capacitate[i + N][t] = b;

        for (int j = 1; j <= N; ++j) {
            graf[i].push_back(j + N);
            graf[j + N].push_back(i);
            capacitate[i][j + N] = 1;
        }
    }

    int flux_maxim = fordFulkerson(s, t);

    fout << flux_maxim << "\n";
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; ++j) {
            if (flux[i][j + N] > 0) {
                fout << i << " " << j << "\n";
            }
        }
    }

    fin.close();
    fout.close();
    return 0;
}