Pagini recente » Cod sursa (job #2057762) | Cod sursa (job #3137418) | Cod sursa (job #1861536) | Cod sursa (job #643644) | Cod sursa (job #3188780)
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
const int MAX_NODES = 100;
vector<int> adjacencyList[1 + 2 * MAX_NODES + 1];
bool pathFound;
queue<int> bfsQueue;
int parent[1 + 2 * MAX_NODES + 1];
int capacityMatrix[1 + 2 * MAX_NODES + 1][1 + 2 * MAX_NODES + 1];
// Function for Breadth-First Search to find augmenting paths
void bfs(int numNodes) {
pathFound = false;
for (int i = 0; i <= 2 * numNodes + 1; ++i)
parent[i] = -1;
parent[0] = 0;
bfsQueue.emplace(0);
while (!bfsQueue.empty()) {
int node = bfsQueue.front();
bfsQueue.pop();
for (int i = 0; i < adjacencyList[node].size(); ++i) {
int neighbor = adjacencyList[node][i];
if (parent[neighbor] == -1 && capacityMatrix[node][neighbor] > 0) {
if (neighbor != 2 * numNodes + 1) {
parent[neighbor] = node;
bfsQueue.emplace(neighbor);
} else {
pathFound = true;
}
}
}
}
}
int main(){
int numNodes;
fin >> numNodes;
// Reading capacities from input file
for (int i = 1; i <= numNodes; ++i)
fin >> capacityMatrix[0][i] >> capacityMatrix[numNodes + i][2 * numNodes + 1];
// Setting capacities within the graph
for (int i = 1; i <= numNodes; ++i)
for (int j = numNodes + 1; j <= 2 * numNodes; ++j)
if (numNodes + i != j)
capacityMatrix[i][j] = 1;
// Creating the adjacency list representation of the graph
for (int i = 1; i <= numNodes; ++i) {
adjacencyList[0].emplace_back(i);
adjacencyList[i].emplace_back(0);
}
for (int i = numNodes + 1; i <= 2 * numNodes; ++i) {
adjacencyList[i].emplace_back(2 * numNodes + 1);
adjacencyList[2 * numNodes + 1].emplace_back(i);
}
for (int i = 1; i <= numNodes; ++i) {
for (int j = numNodes + 1; j <= 2 * numNodes; ++j) {
if (numNodes + i != j) {
adjacencyList[i].emplace_back(j);
adjacencyList[j].emplace_back(i);
}
}
}
int maxFlow = 0;
// Finding maximum flow in the graph
while (true) {
bfs(numNodes);
if (!pathFound)
break;
for (int i = 0; i < adjacencyList[2 * numNodes + 1].size(); ++i) {
int neighbor = adjacencyList[2 * numNodes + 1][i];
int minCapacity = 1e9;
parent[2 * numNodes + 1] = neighbor;
for (int currentNode = 2 * numNodes + 1; parent[currentNode] != currentNode; currentNode = parent[currentNode])
minCapacity = min(minCapacity, capacityMatrix[parent[currentNode]][currentNode]);
for (int currentNode = 2 * numNodes + 1; parent[currentNode] != currentNode; currentNode = parent[currentNode]) {
capacityMatrix[parent[currentNode]][currentNode] -= minCapacity;
capacityMatrix[currentNode][parent[currentNode]] += minCapacity;
}
maxFlow += minCapacity;
}
}
// Writing maximum flow to output file
fout << maxFlow << '\n';
// Writing edges carrying maximum flow to output file
for (int i = 1; i <= numNodes; ++i)
for (int j = numNodes + 1; j <= 2 * numNodes; ++j)
if (numNodes + i != j && capacityMatrix[i][j] == 0)
fout << i << ' ' << j - numNodes << '\n';
return 0;
}