Pagini recente » Cod sursa (job #2654512) | Cod sursa (job #1054310) | Cod sursa (job #1792120) | Cod sursa (job #3265067) | Cod sursa (job #3190330)
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#include <cstring>
using namespace std;
const int MAX_NODES = 505;
const int INFINITY_VAL = 0xfffff;
int capacities[MAX_NODES][MAX_NODES];
int flows[MAX_NODES][MAX_NODES];
vector<int> adjacency[MAX_NODES];
int parents[MAX_NODES];
bool visitedNodes[MAX_NODES];
int totalNodes, maxFlowValue, minCapacityValue;
int inDegrees[MAX_NODES];
int outDegrees[MAX_NODES];
queue<int> bfsQueue;
int DEST_NODE;
ifstream inputFile("input_file.in");
ofstream outputFile("output_file.out");
bool performBFS()
{
bfsQueue.push(1);
memset(visitedNodes, false, sizeof(visitedNodes));
visitedNodes[1] = true;
while (!bfsQueue.empty())
{
int current = bfsQueue.front();
bfsQueue.pop();
if (current == DEST_NODE)
continue;
for (int i = 0; i < adjacency[current].size(); ++i)
{
int neighbor = adjacency[current][i];
if (capacities[current][neighbor] == flows[current][neighbor] || visitedNodes[neighbor])
continue;
visitedNodes[neighbor] = true;
bfsQueue.push(neighbor);
parents[neighbor] = current;
}
}
return visitedNodes[DEST_NODE];
}
void solveNetworkFlow()
{
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)
{
capacities[1][i + 1] = outDegrees[i];
adjacency[1].push_back(i + 1);
adjacency[i + 1].push_back(1);
capacities[1 + totalNodes + i][DEST_NODE] = inDegrees[i];
adjacency[i + 1 + totalNodes].push_back(DEST_NODE);
adjacency[DEST_NODE].push_back(i + 1 + totalNodes);
}
for (int i = 1; i <= totalNodes; ++i)
{
for (int j = i + 1; j <= totalNodes; ++j)
{
capacities[i + 1][j + totalNodes + 1] = 1;
adjacency[i + 1].push_back(j + totalNodes + 1);
adjacency[j + totalNodes + 1].push_back(i + 1);
capacities[j + 1][i + totalNodes + 1] = 1;
adjacency[j + 1].push_back(i + totalNodes + 1);
adjacency[i + totalNodes + 1].push_back(j + 1);
}
}
maxFlowValue = 0;
performBFS();
while (performBFS())
{
for (int i = 0; i < adjacency[DEST_NODE].size(); ++i)
{
int current = adjacency[DEST_NODE][i];
if (capacities[current][DEST_NODE] == flows[current][DEST_NODE] || !visitedNodes[current])
continue;
minCapacityValue = INFINITY_VAL;
parents[DEST_NODE] = current;
for (int i = DEST_NODE; i != 1; i = parents[i])
minCapacityValue = min(minCapacityValue, capacities[parents[i]][i] - flows[parents[i]][i]);
if (minCapacityValue == 0)
continue;
for (int i = DEST_NODE; i != 1; i = parents[i])
{
flows[parents[i]][i] += minCapacityValue;
flows[i][parents[i]] -= minCapacityValue;
}
maxFlowValue += minCapacityValue;
}
}
vector<pair<int, int>> resultEdges;
for (int i = 1; i <= totalNodes; ++i)
{
for (int j = 1; j <= totalNodes; ++j)
{
if (i != j && flows[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()
{
solve();
inputFile.close();
outputFile.close();
return 0;
}