Pagini recente » Cod sursa (job #658427) | Cod sursa (job #2372471) | Cod sursa (job #2813573) | Cod sursa (job #454346) | Cod sursa (job #3190325)
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#include <cstring>
using namespace std;
const int MAX_VERTICES = 500;
const int INFINITY_FLOW = 0xffffff;
int capacity[MAX_VERTICES][MAX_VERTICES];
int flow[MAX_VERTICES][MAX_VERTICES];
vector<int> adjacency[MAX_VERTICES];
int parents[MAX_VERTICES];
bool visitedNodes[MAX_VERTICES];
int totalNodes, maxFlowValue, minCapacityValue;
int inDegrees[MAX_VERTICES];
int outDegrees[MAX_VERTICES];
queue<int> bfsTraversal;
int DESTINATION_NODES;
ifstream fileInput("graph.in");
ofstream fileOutput("graph.out");
bool performBFS()
{
bfsTraversal.push(1);
memset(visitedNodes, false, sizeof(visitedNodes));
visitedNodes[1] = true;
while (!bfsTraversal.empty())
{
int currentVertex = bfsTraversal.front();
bfsTraversal.pop();
if (currentVertex == DESTINATION_NODES)
continue;
for (int i = 0; i < adjacency[currentVertex].size(); ++i)
{
int neighbor = adjacency[currentVertex][i];
if (capacity[currentVertex][neighbor] == flow[currentVertex][neighbor] || visitedNodes[neighbor])
continue;
visitedNodes[neighbor] = true;
bfsTraversal.push(neighbor);
parents[neighbor] = currentVertex;
}
}
return visitedNodes[DESTINATION_NODES];
}
void resolve()
{
fileInput >> totalNodes;
DESTINATION_NODES = totalNodes * 2 + 2;
for (int i = 1; i <= totalNodes; ++i)
{
fileInput >> outDegrees[i] >> inDegrees[i];
}
for (int i = 1; i <= totalNodes; ++i)
{
capacity[1][i + 1] = outDegrees[i];
adjacency[1].push_back(i + 1);
adjacency[i + 1].push_back(1);
capacity[1 + totalNodes + i][DESTINATION_NODES] = inDegrees[i];
adjacency[i + 1 + totalNodes].push_back(DESTINATION_NODES);
adjacency[DESTINATION_NODES].push_back(i + 1 + totalNodes);
}
for (int i = 1; i <= totalNodes; ++i)
{
for (int j = i + 1; j <= totalNodes; ++j)
{
capacity[i + 1][j + totalNodes + 1] = 1;
adjacency[i + 1].push_back(j + totalNodes + 1);
adjacency[j + totalNodes + 1].push_back(i + 1);
capacity[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[DESTINATION_NODES].size(); ++i)
{
int currentVertex = adjacency[DESTINATION_NODES][i];
if (capacity[currentVertex][DESTINATION_NODES] == flow[currentVertex][DESTINATION_NODES] || !visitedNodes[currentVertex])
continue;
minCapacityValue = INFINITY_FLOW;
parents[DESTINATION_NODES] = currentVertex;
for (int j = DESTINATION_NODES; j != 1; j = parents[j])
minCapacityValue = min(minCapacityValue, capacity[parents[j]][j] - flow[parents[j]][j]);
if (minCapacityValue == 0)
continue;
for (int j = DESTINATION_NODES; j != 1; j = parents[j])
{
flow[parents[j]][j] += minCapacityValue;
flow[j][parents[j]] -= 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 && flow[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()
{
resolve();
fileInput.close();
fileOutput.close();
return 0;
}