Pagini recente » Cod sursa (job #2758673) | Cod sursa (job #2691085) | Cod sursa (job #2644376) | Cod sursa (job #1911852) | Cod sursa (job #3190332)
#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 isNodeVisited[MAX_VERTICES];
int totalNodes, maximumFlow, minimumCapacity;
int inDegrees[MAX_VERTICES];
int outDegrees[MAX_VERTICES];
queue<int> bfsTraversal;
int DESTINATION_NODE;
ifstream fileInput("map.in");
ofstream fileOutput("map.out");
bool performBFS()
{
bfsTraversal.push(1);
memset(isNodeVisited, false, sizeof(isNodeVisited));
isNodeVisited[1] = true;
while (!bfsTraversal.empty())
{
int current = bfsTraversal.front();
bfsTraversal.pop();
if (current == DESTINATION_NODE)
continue;
for (int i = 0; i < adjacencyList[current].size(); ++i)
{
int neighbor = adjacencyList[current][i];
if (networkCapacity[current][neighbor] == networkFlow[current][neighbor] || isNodeVisited[neighbor])
continue;
isNodeVisited[neighbor] = true;
bfsTraversal.push(neighbor);
parentNode[neighbor] = current;
}
}
return isNodeVisited[DESTINATION_NODE];
}
void computeMaxFlow()
{
fileInput >> totalNodes;
DESTINATION_NODE = totalNodes * 2 + 2;
for (int i = 1; i <= totalNodes; ++i)
{
fileInput >> 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][DESTINATION_NODE] = inDegrees[i];
adjacencyList[i + 1 + totalNodes].push_back(DESTINATION_NODE);
adjacencyList[DESTINATION_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);
}
}
maximumFlow = 0;
performBFS();
while (performBFS())
{
for (int i = 0; i < adjacencyList[DESTINATION_NODE].size(); ++i)
{
int current = adjacencyList[DESTINATION_NODE][i];
if (networkCapacity[current][DESTINATION_NODE] == networkFlow[current][DESTINATION_NODE] || !isNodeVisited[current])
continue;
minimumCapacity = INFINITY_FLOW;
parentNode[DESTINATION_NODE] = current;
for (int i = DESTINATION_NODE; i != 1; i = parentNode[i])
minimumCapacity = min(minimumCapacity, networkCapacity[parentNode[i]][i] - networkFlow[parentNode[i]][i]);
if (minimumCapacity == 0)
continue;
for (int i = DESTINATION_NODE; i != 1; i = parentNode[i])
{
networkFlow[parentNode[i]][i] += minimumCapacity;
networkFlow[i][parentNode[i]] -= minimumCapacity;
}
maximumFlow += minimumCapacity;
}
}
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});
}
}
}
fileOutput << resultEdges.size() << "\n";
for (auto edge : resultEdges)
{
fileOutput << edge.first << " " << edge.second << "\n";
}
}
int main()
{
computeMaxFlow();
fileInput.close();
fileOutput.close();
return 0;
}