Pagini recente » Cod sursa (job #1174226) | Cod sursa (job #1747268) | Cod sursa (job #1425145) | Cod sursa (job #2856732) | Cod sursa (job #3188034)
#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>
#include <fstream>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
// Structura pentru reprezentarea unei muchii
struct Edge {
int destination; // nodul destinatar
int capacity; // capacitatea maximă a muchiei
int flow; // fluxul curent pe muchie
int residual; // capacitatea reziduală a muchiei
Edge(int v, int c) {
destination = v;
capacity = c;
flow = 0;
residual = capacity;
}
};
class Graph {
int V; // numărul de noduri
vector<vector<Edge>> adj; // listă de adiacență pentru reprezentarea grafului
public:
Graph(const int& V) : V(V), adj(V + 2) {}
// Adaugă o muchie în graf
void AddEdge(const int& u, const int& v, const int& c) {
Edge e_u(v, c);
Edge e_v(u, 0);
adj[u].push_back(e_u);
adj[v].push_back(e_v);
}
// Algoritmul lui Edmonds-Karp pentru calcularea fluxului maxim într-o rețea
int EdmondsKarp(int source, int sink) {
int maxFlow = 0;
while (true) {
vector<int> parent(V + 2, -1);
queue<pair<int, int>> q;
q.push({source, INT_MAX});
while (!q.empty()) {
int u = q.front().first;
int minCapacity = q.front().second;
q.pop();
for (const Edge& e : adj[u]) {
int v = e.destination;
if (parent[v] == -1 && e.residual > 0) {
parent[v] = u;
// Actualizăm capacitatea minimă pe drum
int newMinCapacity = min(minCapacity, e.residual);
q.push({v, newMinCapacity});
if (v == sink) {
int pathFlow = newMinCapacity;
int current = v;
while (current != source) {
int previous = parent[current];
for (Edge& edge : adj[previous]) {
if (edge.destination == current) {
edge.residual -= pathFlow;
edge.flow += pathFlow;
break;
}
}
for (Edge& reverseEdge : adj[current]) {
if (reverseEdge.destination == previous) {
reverseEdge.residual += pathFlow;
break;
}
}
current = previous;
}
maxFlow += pathFlow;
break;
}
}
}
}
if (parent[sink] == -1) {
break;
}
}
return maxFlow;
}
// Afișează detaliile muchiilor (pentru debugare)
void Afisare() {
for (int i = 0; i <= V + 1; i++)
for (auto e : adj[i])
cout << i << " " << e.destination << " " << e.capacity << " " << e.flow << " " << e.residual << "\n";
}
// Afișează drumurile rezultate (muchii cu capacitatea maximă)
void Roads() {
for (int i = 1; i <= V / 2; i++) {
for (auto e : adj[i]) {
if (e.residual == 0 && e.capacity)
g << i << " " << e.destination - V / 2 << endl;
}
}
}
};
int main() {
int N;
f >> N;
int source = 0;
int sink = 2 * N + 1;
Graph G(2 * N);
int out, in;
// Citirea datelor și construirea grafului
for (int i = 1; i <= N; i++) {
f >> out >> in;
G.AddEdge(source, i, out);
G.AddEdge(N + i, sink, in);
for (int j = 1; j <= N; j++)
if (i != j)
G.AddEdge(i, N + j, 1);
}
// Calculul fluxului maxim și afișarea drumurilor rezultate
g << G.EdmondsKarp(source, sink) << endl;
G.Roads();
return 0;
}