Pagini recente » Cod sursa (job #2988667) | Cod sursa (job #2576736) | Cod sursa (job #533826) | Cod sursa (job #1129108) | Cod sursa (job #3190174)
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <climits>
#include <tuple>
#include <queue>
#include <algorithm>
class Node {
public:
int id;
std::vector<std::tuple<int, int>> edges;
explicit Node(int id) : id(id) {}
};
class Edge {
public:
int start, end;
int capacity;
Edge(int s, int e, int c) : start(s), end(e), capacity(c){}
};
class Graph {
public:
int N, K;
std::vector<Node> nodes;
std::vector<Edge> edges;
explicit Graph(int n, int k = 0) : N(n), K(k) {
for (int i = 0; i < n; ++i) {
nodes.emplace_back(i);
}
}
void addNode(int id) {
nodes.emplace_back(id);
}
void addEdge(int start, int end, int capacity) {
edges.emplace_back(start, end, capacity);
nodes[start].edges.emplace_back(end, capacity);
for (auto& edge : nodes[end].edges) {
if (std::get<0>(edge) == start) {
return;
}
}
nodes[end].edges.emplace_back(start, 0); // Add the reverse edge with 0 capacity
}
void addDirectedEdge(int start, int end, int capacity) {
edges.emplace_back(start, end, capacity);
nodes[start].edges.emplace_back(end, capacity);
}
int fordFulkerson(int source, int sink) {
int maxFlow = 0;
while (true) {
// Find augmenting path using BFS
std::vector<int> parent(N, -1);
std::queue<std::pair<int, int>> q; // (node, min_capacity)
q.push({source, INT_MAX});
while (!q.empty()) {
int current = q.front().first;
int minCapacity = q.front().second;
q.pop();
for (const auto& edge : nodes[current].edges) {
int neighbor = std::get<0>(edge);
int capacity = std::get<1>(edge);
if (parent[neighbor] == -1 && capacity > 0) {
parent[neighbor] = current;
int newMinCapacity = std::min(minCapacity, capacity);
if (neighbor == sink) {
// Found augmenting path
while (neighbor != source) {
int prev = parent[neighbor];
for (auto& edge : nodes[prev].edges) {
if (std::get<0>(edge) == neighbor) {
std::get<1>(edge) -= newMinCapacity;
break;
}
}
bool reverseEdgeFound = false;
for (auto& edge : nodes[neighbor].edges) {
if (std::get<0>(edge) == prev) {
std::get<1>(edge) += newMinCapacity;
reverseEdgeFound = true;
break;
}
}
if (!reverseEdgeFound) {
nodes[neighbor].edges.emplace_back(prev, newMinCapacity);
}
neighbor = prev;
}
maxFlow += newMinCapacity;
break;
}
q.push({neighbor, newMinCapacity});
}
}
}
// No more augmenting paths
if (parent[sink] == -1) {
break;
}
}
return maxFlow;
}
};
int main() {
std::ifstream fin("harta.in");
std::ofstream fout("harta.out");
// std::istream &in = fin;
// std::ostream &out = fout;
std::istream &in = std::cin;
std::ostream &out = std::cout;
int n;
in >> n;
// Graf g(2 * N + 2);
//
// for (int i = 0; i < N; i++) {
// fin >> x >> y;
// g.adauga_capacitate(2 * N, i, x);
// g.adauga_capacitate(i + N, 2 * N + 1, y);
//
// for (int j = 0; j < N; j++) {
// if (i != j)
// g.adauga_capacitate(i, j + N, 1);
// }
// }
// Create a graph given in the above diagram
Graph graph(2 * n + 2);
// Add edges
std::vector<std::vector<int>> capacity(2 * n + 2, std::vector<int>(2 * n + 2, 0));
for(int i = 0; i < n; i++)
{
int x, y;
in >> x >> y;
capacity[2 * n][i] = x;
capacity[i + n][2 * n + 1] = y;
for(int j = 0; j < n; j++)
if(i != j)
capacity[i][j + n] = 1;
}
// Add edges
for (int i = 0; i < 2 * n + 2; ++i) {
for (int j = 0; j < 2 * n + 2; ++j) {
if (capacity[i][j] > 0) {
graph.addDirectedEdge(i, j, capacity[i][j]);
graph.addDirectedEdge(j, i, capacity[i][j]);
}
}
}
// Call the Ford-Fulkerson algorithm
int source = 0;
int sink = 2 * n + 1;
int maxFlow = graph.fordFulkerson(source, sink);
out << maxFlow << std::endl;
return 0;
}