Pagini recente » Cod sursa (job #1689373) | Cod sursa (job #2234569) | Cod sursa (job #2711373) | Cod sursa (job #2958277) | Cod sursa (job #2960828)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <climits>
using namespace std;
ifstream fin ("harta.in");
ofstream fout ("harta.out");
int n, flow, maxflow, element;
vector<bool> visited;
vector<int> parent;
vector<vector<int>> capacity;
queue<int> q;
bool bfs() {
fill(visited.begin(), visited.end(), 0);
fill(parent.begin(), parent.end(), 0);
visited[0] = 1;
parent[0] = -1;
q.push(0);
while (!q.empty()) {
int currentNode = q.front();
q.pop();
if (currentNode == 2*n+1) {
return 1;
}
for (int i=1; i<=2*n+1; i++) {
if (!visited[i] && capacity[currentNode][i] > 0) {
q.push(i);
visited[i] = 1;
parent[i] = currentNode;
}
}
}
return 0;
}
void edmondskarp () {
while (bfs()) {
for (int i=1; i<=n; i++) {
if (visited[n+i] && capacity[n+i][2*n+1] > 0) {
flow = INT_MAX;
parent[2*n+1] = n+i;
for (element = 2*n+1; element!=0; element = parent[element])
flow = min (flow, capacity[parent[element]][element]);
if (flow == 0) continue;
for (element = 2*n+1; element!=0; element = parent[element]) {
capacity[element][parent[element]] += flow;
capacity[parent[element]][element] -= flow;
}
maxflow += flow;
}
}
}
}
int main () {
fin >> n;
visited.resize(2*n+2,0);
parent.resize(2*n+2, 0);
capacity.resize(2*n+2, vector<int>(2*n+2, 0));
for (int i=1; i<=n; i++) {
int x,y;
fin >> x >> y;
capacity[0][i] = x;
capacity[i+n][2*n+1] = y;
for (int j=1; j<=n; j++) {
if (i!=j) {
capacity[i][j+n] = 1;
}
}
}
edmondskarp();
fout << maxflow << "\n";
for (int i=1; i<=n; i++) {
for (int j=1; j<=n; j++) {
if (capacity[i][n+j] == 0 && i!=j) {
fout << i << " " << j << "\n";
}
}
}
return 0;
}