Pagini recente » Cod sursa (job #2339037) | Cod sursa (job #2095987) | Cod sursa (job #879407) | Cod sursa (job #1842978) | Cod sursa (job #2960062)
#include <iostream>
#include <fstream>
#include <list>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
// Declare input and output files
ifstream f("harta.in");
ofstream g("harta.out");
// Declare variables
int n, s, t;
vector < vector < int >> capacity;
list < int > *adjList; // Pointer to an array of linked lists to store adjacency lists
vector < int > parent; // Vector to store the BFS tree
// Function to perform BFS on the residual graph
bool bfs() {
// Assign all values in the parent vector to 0
parent.assign(t + 1, 0);
// Declare a queue to store nodes during BFS
queue < int > q;
// Push the source node onto the queue
q.push(s);
// While the queue is not empty
while (!q.empty()) {
// Get the first element in the queue
int firstInQueue = q.front();
q.pop();
// If the first element in the queue is the sink node, return true
if (firstInQueue == t) {
return true;
}
// For each adjacent node to the current node
for (auto const& adjNode: adjList[firstInQueue]) {
// Get the capacity of the edge between the current node and the adjacent node
int currentCapacity = capacity[firstInQueue][adjNode];
// If the capacity is greater than 0 and the parent of the adjacent node has not been set
if (currentCapacity > 0 && parent[adjNode] == 0) {
// Set the parent of the adjacent node to the current node
parent[adjNode] = firstInQueue;
// Push the adjacent node onto the queue
q.push(adjNode);
}
}
}
// Return false if we reach this point, as the sink node has not been found
return false;
}
// Function to compute the maximum flow using Edmonds-Karp algorithm
int edmondsKarp() {
// Initialize the maximum flow to 0
int maxFlow = 0;
// While there is a path from the source to the sink in the residual graph
while (bfs()) {
// Initialize the current flow to the maximum possible value
int currentFlow = INT_MAX;
// For each node in the path from the sink to the source
for (int i = t; i != s; i = parent[i]) {
// Find the minimum capacity of the edges in the path
currentFlow = min(currentFlow, capacity[parent[i]][i]);
}
// For each node in the path from the sink to the source
for (int i = t; i != s; i = parent[i]) {
capacity[parent[i]][i] -= currentFlow;
capacity[i][parent[i]] += currentFlow;
}
// Add the current flow to the maximum flow
maxFlow += currentFlow;
}
// Return the maximum flow
return maxFlow;
}
int main() {
f >> n;
t = 2 * n + 1;
adjList = new list < int > [t + 1];
parent.resize(t + 1);
capacity.resize(t + 1, vector < int > (t + 1));
for (int i = 1; i <= n; ++i) {
int x, y;
f >> x >> y;
adjList[s].push_back(i); // Add an edge from the source to the node with capacity x
adjList[i].push_back(s); // Add an edge from the node to the source with capacity 0
capacity[s][i] = x; // Set the capacity of the edge from the source to the node to x
adjList[i + n].push_back(t); // Add an edge from the node to the sink with capacity y
adjList[t].push_back(i + n); // Add an edge from the sink to the node with capacity 0
capacity[i + n][t] = y; // Set the capacity of the edge from the node to the sink to y
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (i != j) {
adjList[i].push_back(j + n);
adjList[j + n].push_back(i);
capacity[i][j + n] = 1;
}
}
}
g << edmondsKarp() << '\n';
for (int i = 1; i <= n; ++i) {
for (auto const& node: adjList[i]) {
if (node != s && node != t && capacity[i][node] == 0) {
g << i << " " << node - n << '\n';
}
}
}
}