Pagini recente » Cod sursa (job #1626054) | Cod sursa (job #1095497) | Cod sursa (job #1472985) | Borderou de evaluare (job #2079085) | Cod sursa (job #3189908)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
const int MAX_VAL = 0x3f3f3f3f;
int nodes, capacity[220][220], parent[220], flow[220][220], max_flow;
// Funcția care calculează fluxul maxim folosind algoritmul Edmonds-Karp.
void maxFlow(int source, int destination);
// Funcția care parcurge graful folosind BFS pentru a identifica un drum de creștere.
bool bfs(int source, int destination);
// Funcție utilitară pentru a găsi minimul dintre două valori.
int findMin(int a, int b);
int main() {
// Deschidere fișiere pentru citire și scriere.
std::ifstream fin("harta.in");
std::ofstream fout("harta.out");
// Citirea numărului de noduri din fișier.
fin >> nodes;
int startVal, endVal;
for (int i = 1; i <= nodes; ++i) {
// Citirea valorilor pentru fiecare nod și inițializarea capacităților.
fin >> startVal >> endVal;
capacity[0][i] = startVal;
capacity[i + nodes][2 * nodes + 1] = endVal;
for (int j = nodes + 1; j <= 2 * nodes; ++j) {
capacity[i][j] = 1;
}
capacity[i][i + nodes] = 0; // Inițializare fluxuri.
}
// Apelul funcției pentru calculul fluxului maxim.
maxFlow(0, 2 * nodes + 1);
// Calcularea numărului de muchii care transportă flux.
int result = 0;
for (int i = 1; i <= nodes; ++i) {
for (int j = 1; j <= nodes; ++j) {
if (flow[i][j + nodes]) {
++result;
}
}
}
// Scrierea rezultatelor în fișierul de ieșire.
fout << result << "\n";
for (int i = 1; i <= nodes; ++i) {
for (int j = 1; j <= nodes; ++j) {
if (flow[i][j + nodes]) {
fout << i << " " << j << "\n";
}
}
}
// Închiderea fișierelor.
fin.close();
fout.close();
return 0;
}
// Implementarea funcției pentru calculul fluxului maxim.
void maxFlow(int source, int destination) {
max_flow = 0;
while (bfs(source, destination)) {
int min_flow = MAX_VAL;
int current = destination;
while (current != source) {
min_flow = findMin(min_flow, capacity[parent[current]][current] - flow[parent[current]][current]);
current = parent[current];
}
current = destination;
while (current != source) {
flow[parent[current]][current] += min_flow;
flow[current][parent[current]] -= min_flow;
current = parent[current];
}
max_flow += min_flow;
}
}
// Implementarea funcției BFS pentru parcurgerea grafului.
bool bfs(int source, int destination) {
std::queue<int> q;
memset(parent, -1, sizeof(parent));
parent[source] = -2;
q.push(source);
while (!q.empty()) {
int current = q.front();
q.pop();
for (int i = 0; i <= 2 * nodes + 1; ++i) {
if (parent[i] == -1 && capacity[current][i] > flow[current][i]) {
parent[i] = current;
q.push(i);
if (i == destination) {
return true;
}
}
}
}
return false;
}
// Implementarea funcției utilitare pentru găsirea minimului dintre două valori.
int findMin(int a, int b) {
return (a < b) ? a : b;
}