Pagini recente » Cod sursa (job #2865217) | Cod sursa (job #354995) | Cod sursa (job #1119756) | Cod sursa (job #2828492) | Cod sursa (job #3188832)
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <fstream>
#include <cstring>
using namespace std;
const int MAX_N = 1005;
ifstream f("harta.in");
ofstream fout("harta.out");
struct Edge {
int v, capacity, flowPassed;
};
vector<vector<Edge>> graph(MAX_N * 2 + 2);
vector<int> parent(MAX_N * 2 + 2);
bool bfs(int s, int t) {
fill(parent.begin(), parent.end(), -1);
vector<bool> visited(graph.size(), false);
queue<int> q;
q.push(s);
visited[s] = true;
while (!q.empty()) {
int u = q.front();
q.pop();
cout<<u<<" ";
for (auto &edge : graph[u]) {
int v = edge.v;
// Verifică dacă nodul nu a fost vizitat și dacă există capacitate disponibilă
if (!visited[v] && edge.capacity - edge.flowPassed > 0) {
q.push(v);
parent[v] = u;
visited[v] = true;
if (v == t) {
return true; // Calea a fost găsită
}
}
}
}
return false; // Nu s-a găsit nicio cale
}
int edmondsKarp(int s, int t) {
int max_flow = 0;
while (bfs(s, t)) {
int path_flow = INT_MAX;
// Determinați fluxul maxim pe calea găsită
for (int v = t; v != s; v = parent[v]) {
int u = parent[v];
for (auto &edge : graph[u]) {
if (edge.v == v && edge.capacity - edge.flowPassed > 0) {
path_flow = min(path_flow, edge.capacity - edge.flowPassed);
break;
}
}
}
cout << "Calea gasita cu flux: " << path_flow << endl;
// Actualizăm capacitatea rămasă și fluxul trecut pe muchii și muchiile inverse
for (int v = t; v != s; v = parent[v]) {
int u = parent[v];
// Căutăm muchia directă și inversă pentru a actualiza fluxul
for (auto &edge : graph[u]) {
if (edge.v == v) {
edge.flowPassed += path_flow; // Actualizare muchie directă
// Căutăm și actualizăm muchia inversă
for (auto &backEdge : graph[v]) {
if (backEdge.v == u) {
backEdge.flowPassed -= path_flow; // Actualizare muchie inversă
break;
}
}
break;
}
}
}
max_flow += path_flow;
}
return max_flow;
}
int main() {
int N; // Numărul de orașe
f >> N;
int source = 0; // Nodul sursă
int sink = 2 * N + 1; // Nodul destinație
// Construirea graficului
for (int i = 1; i <= N; ++i) {
int out, in;
f >> out >> in;
// De la sursă la orașul de plecare
graph[source].push_back({i, out, 0});
// De la orașul de sosire la destinație
graph[N + i].push_back({sink, in, 0});
}
// Muchii între orașele de plecare și sosire
for (int i = 1; i <= N; ++i) {
for (int j = N + 1; j <= 2 * N; ++j) {
if (i != j - N) {
graph[i].push_back({j, 1, 0}); // Adaugă muchia cu capacitatea 1
}
}
}
// Aplicarea algoritmului Edmonds-Karp pentru a găsi fluxul maxim
int maxFlow = edmondsKarp(source, sink);
// Interpretăm rezultatele pentru a găsi drumurile individuale
fout << maxFlow << endl;
for (int i = 1; i <= N; ++i) {
for (auto &edge : graph[i]) {
if (edge.v > N && edge.v <= 2 * N && edge.flowPassed > 0) {
fout << i << " " << (edge.v - N) << endl;
}
}
}
return 0;
}