Pagini recente » Cod sursa (job #903509) | Cod sursa (job #553827) | Infoarena Monthly 2012, Runda 10 - Clasament | Cod sursa (job #300415) | Cod sursa (job #3189854)
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#include <cstring>
using namespace std;
const int MAX_NODES = 500;
const int INF = 0xffffff;
int capacity[MAX_NODES][MAX_NODES];
int flow[MAX_NODES][MAX_NODES];
vector<int> graph[MAX_NODES];
int parent[MAX_NODES];
bool visited[MAX_NODES];
int nodeCount, maxFlow, minCapacity;
int indegree[MAX_NODES];
int outdegree[MAX_NODES];
ifstream fin("harta.in");
ofstream fout("harta.out");
bool bfs(int source, int dest) {
memset(visited, false, sizeof(visited));
queue<int> bfsQueue;
bfsQueue.push(source);
visited[source] = true;
while (!bfsQueue.empty()) {
int current = bfsQueue.front();
bfsQueue.pop();
for (int neighbor : graph[current]) {
if (!visited[neighbor] && capacity[current][neighbor] > flow[current][neighbor]) {
bfsQueue.push(neighbor);
parent[neighbor] = current;
visited[neighbor] = true;
}
}
}
return visited[dest];
}
void augmentFlow(int dest) {
for (int i = 0; i < graph[dest].size(); ++i) {
int current = graph[dest][i];
if (!visited[current] || capacity[current][dest] == flow[current][dest])
continue;
minCapacity = INF;
for (int node = dest; node != 1; node = parent[node])
minCapacity = min(minCapacity, capacity[parent[node]][node] - flow[parent[node]][node]);
if (minCapacity == 0)
continue;
for (int node = dest; node != 1; node = parent[node]) {
flow[parent[node]][node] += minCapacity;
flow[node][parent[node]] -= minCapacity;
}
maxFlow += minCapacity;
}
}
void initializeGraph() {
fin >> nodeCount;
int source = 1;
int dest = nodeCount * 2 + 2;
for (int i = 1; i <= nodeCount; ++i) {
fin >> outdegree[i] >> indegree[i];
capacity[source][i + 1] = outdegree[i];
graph[source].push_back(i + 1);
graph[i + 1].push_back(source);
capacity[i + 1 + nodeCount][dest] = indegree[i];
graph[i + 1 + nodeCount].push_back(dest);
graph[dest].push_back(i + 1 + nodeCount);
}
for (int i = 1; i <= nodeCount; ++i) {
for (int j = 1; j <= nodeCount; ++j) {
if (i != j) {
capacity[i + 1][j + nodeCount + 1] = 1;
graph[i + 1].push_back(j + nodeCount + 1);
graph[j + nodeCount + 1].push_back(i + 1);
}
}
}
}
void calculateMaxFlow(int source, int dest) {
maxFlow = 0;
while (bfs(source, dest)) {
augmentFlow(dest);
}
}
vector<pair<int, int>> extractResultEdges(int nodeCount) {
vector<pair<int, int>> resultEdges;
for (int i = 1; i <= nodeCount; ++i) {
for (int j = 1; j <= nodeCount; ++j) {
if (i != j && flow[i + 1][j + nodeCount + 1] == 1) {
resultEdges.push_back({i, j});
}
}
}
return resultEdges;
}
void writeResult(const vector<pair<int, int>>& resultEdges) {
fout << resultEdges.size() << "\n";
for (const auto& edge : resultEdges) {
fout << edge.first << " " << edge.second << "\n";
}
}
int main() {
initializeGraph();
calculateMaxFlow(1, nodeCount * 2 + 2);
vector<pair<int, int>> resultEdges = extractResultEdges(nodeCount);
writeResult(resultEdges);
fin.close();
fout.close();
return 0;
}