Pagini recente » Cod sursa (job #40322) | Cod sursa (job #57765) | Cod sursa (job #839030) | Cod sursa (job #45343) | Cod sursa (job #2960073)
#include <iostream>
#include <fstream>
#include <list>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
// Declare input and output files
ifstream f("harta.in");
ofstream g("harta.out");
int n, s, t;
vector < int > parent;
vector< vector < int >> capacity;
vector< vector < int >> adjNodeList;
bool bfs() {
vector < bool > visited(t + 1);
queue < int > q;
q.push(s);
visited[s] = true;
parent[s] = -1;
while (!q.empty()) {
int firstInQueue = q.front();
q.pop();
for (auto const& adjNode: adjNodeList[firstInQueue]) {
if (!visited[adjNode] && capacity[firstInQueue][adjNode]) {
parent[adjNode] = firstInQueue;
if ( adjNode == t) {
return true;
}
visited[adjNode] = true;
q.push(adjNode);
}
}
}
return false;
}
int edmondsKarp() {
int maxFlow = 0;
while (bfs()) {
int currentFlow = INT_MAX;
for (int x = t; x!=s; x = parent[x]) {
int y = parent[x];
if (capacity[y][x] < currentFlow) {
currentFlow = capacity[y][x];
}
}
for (int x = t; x != s; x = parent[x]) {
int y = parent[x];
capacity[y][x] -= currentFlow;
capacity[x][y] += currentFlow;
}
maxFlow += currentFlow;
}
return maxFlow;
}
int main() {
f >> n;
t = 2 * n + 1;
adjNodeList.resize(t + 1);
parent.resize(t + 1);
capacity.resize(t + 1, vector < int >(t + 1));
for (int i = 1; i <= n; ++i) {
int x, y;
f >> x >> y;
adjNodeList[s].push_back(i);
adjNodeList[i].push_back(s);
capacity[s][i] = x;
adjNodeList[n + i].push_back(t);
adjNodeList[t].push_back(n + i);
capacity[n + i][t] = y;
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (i != j) {
adjNodeList[i].push_back(n + j);
adjNodeList[n + j].push_back(i);
capacity[i][n + j]=1;
}
}
}
g << edmondsKarp() << '\n';
for (int i = 1; i <= n; ++i) {
for (auto const& node: adjNodeList[i]) {
if (node != s && !capacity[i][node] && node != t) {
g << i << " " << node - n << '\n';
}
}
}
return 0;
}