Pagini recente » Cod sursa (job #1472946) | Cod sursa (job #907350) | Statistici Madalina (madalina023) | Cod sursa (job #2823335) | Cod sursa (job #3190334)
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#include <cstring>
using namespace std;
const int MAX_VERTICES = 500;
const int INFINITY_FLOW = 0xffffff;
int networkCapacity[MAX_VERTICES][MAX_VERTICES];
int networkFlow[MAX_VERTICES][MAX_VERTICES];
vector<int> adjacencyList[MAX_VERTICES];
int parentNode[MAX_VERTICES];
bool nodeVisited[MAX_VERTICES];
int totalNodes, maxFlow, minCapacity;
int inDegrees[MAX_VERTICES];
int outDegrees[MAX_VERTICES];
queue<int> bfsTraversal;
int DEST_NODE;
ifstream inputFile("input.in");
ofstream outputFile("output.out");
bool breadthFirstSearch()
{
bfsTraversal.push(1);
memset(nodeVisited, false, sizeof(nodeVisited));
nodeVisited[1] = true;
while (!bfsTraversal.empty())
{
int current = bfsTraversal.front();
bfsTraversal.pop();
if (current == DEST_NODE)
continue;
for (int i = 0; i < adjacencyList[current].size(); ++i)
{
int neighbor = adjacencyList[current][i];
if (networkCapacity[current][neighbor] == networkFlow[current][neighbor] || nodeVisited[neighbor])
continue;
nodeVisited[neighbor] = true;
bfsTraversal.push(neighbor);
parentNode[neighbor] = current;
}
}
return nodeVisited[DEST_NODE];
}
void maxFlowAlgorithm()
{
inputFile >> totalNodes;
DEST_NODE = totalNodes * 2 + 2;
for (int i = 1; i <= totalNodes; ++i)
{
inputFile >> outDegrees[i] >> inDegrees[i];
}
for (int i = 1; i <= totalNodes; ++i)
{
networkCapacity[1][i + 1] = outDegrees[i];
adjacencyList[1].push_back(i + 1);
adjacencyList[i + 1].push_back(1);
networkCapacity[1 + totalNodes + i][DEST_NODE] = inDegrees[i];
adjacencyList[i + 1 + totalNodes].push_back(DEST_NODE);
adjacencyList[DEST_NODE].push_back(i + 1 + totalNodes);
}
for (int i = 1; i <= totalNodes; ++i)
{
for (int j = i + 1; j <= totalNodes; ++j)
{
networkCapacity[i + 1][j + totalNodes + 1] = 1;
adjacencyList[i + 1].push_back(j + totalNodes + 1);
adjacencyList[j + totalNodes + 1].push_back(i + 1);
networkCapacity[j + 1][i + totalNodes + 1] = 1;
adjacencyList[j + 1].push_back(i + totalNodes + 1);
adjacencyList[i + totalNodes + 1].push_back(j + 1);
}
}
maxFlow = 0;
breadthFirstSearch();
while (breadthFirstSearch())
{
for (int i = 0; i < adjacencyList[DEST_NODE].size(); ++i)
{
int current = adjacencyList[DEST_NODE][i];
if (networkCapacity[current][DEST_NODE] == networkFlow[current][DEST_NODE] || !nodeVisited[current])
continue;
minCapacity = INFINITY_FLOW;
parentNode[DEST_NODE] = current;
for (int i = DEST_NODE; i != 1; i = parentNode[i])
minCapacity = min(minCapacity, networkCapacity[parentNode[i]][i] - networkFlow[parentNode[i]][i]);
if (minCapacity == 0)
continue;
for (int i = DEST_NODE; i != 1; i = parentNode[i])
{
networkFlow[parentNode[i]][i] += minCapacity;
networkFlow[i][parentNode[i]] -= minCapacity;
}
maxFlow += minCapacity;
}
}
vector<pair<int, int>> resultEdges;
for (int i = 1; i <= totalNodes; ++i)
{
for (int j = 1; j <= totalNodes; ++j)
{
if (i != j && networkFlow[i + 1][j + totalNodes + 1] == 1)
{
resultEdges.push_back({i, j});
}
}
}
outputFile << resultEdges.size() << "\n";
for (auto edge : resultEdges)
{
outputFile << edge.first << " " << edge.second << "\n";
}
}
int main()
{
maxFlowAlgorithm();
inputFile.close();
outputFile.close();
return 0;
}