Pagini recente » Cod sursa (job #1986088) | Cod sursa (job #2672835) | Cod sursa (job #2962370)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("harta.in");
ofstream fout ("harta.out");
int parent[202], capacity[202][202], n, m, nod, flow, maxFlow, i, j;
int currentNode;
bool visited[202];
queue<int> q;
bool bfs() {
memset(parent, 0, sizeof(parent));
memset(visited, false, sizeof(visited));
q.push(0);
visited[0] = true;
parent[0] = -1;
while (!q.empty()) {
currentNode = q.front();
q.pop();
if (currentNode == 2*n+1)
return true;
for (i=1; i<=2*n+1; i++) {
if (!visited[i] && capacity[currentNode][i] > 0) {
q.push(i);
visited[i] = true;
parent[i] = currentNode;
}
}
}
return false;
}
void edmondskarp() {
while (bfs()) {
for (i=1; i<=n; i++) {
if (visited[n+i] && capacity[n+i][2*n+1] > 0) {
flow = 1000000;
parent[2*n+1] = n+i;
for (nod=2*n+1; nod!=0; nod=parent[nod])
flow = min(flow, capacity[parent[nod]][nod]);
if (flow == 0)
continue;
for (nod=2*n+1; nod!=0; nod=parent[nod]) {
capacity[parent[nod]][nod] -= flow;
capacity[nod][parent[nod]] += flow;
}
maxFlow += flow;
}
}
}
}
int main() {
fin >> n;
int x, y;
for (i=1; i<=n; i++) {
fin >> x >> y;
capacity[0][i] = x;
capacity[n+i][2*n+1] = y;
for (j=1; j<=n; j++)
if (i != j)
capacity[i][n+j] = 1;
}
edmondskarp();
fout << maxFlow << '\n';
for (i=1; i<=n; i++) {
for (j=1; j<=n; j++)
if (capacity[i][n + j] == 0 && i!=j)
fout << i << " " << j << '\n';
}
return 0;
}