Pagini recente » Cod sursa (job #2097992) | Cod sursa (job #985008) | Cod sursa (job #402245) | Cod sursa (job #1623278) | Cod sursa (job #2960484)
#include <bits/stdc++.h>
#define inf INT_MAX
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
int tata[220], v[220][220], in[220], out[220], n, nod, flow, max_flow;
bool vizitat[220];
bool bfs() {
queue<int> q;
memset(tata, 0, sizeof(tata));
memset(vizitat, false, sizeof(vizitat));
q.push(0);
vizitat[0] = true;
tata[0] = -1;
while (!q.empty()) {
int front = q.front();
q.pop();
if (front == 2 * n + 1)
return true;
for (int i = 1; i <= 2 * n + 1; i++) {
if (!vizitat[i] && v[front][i] > 0) {
q.push(i);
vizitat[i] = true;
tata[i] = front;
}
}
}
return false;
}
void reglare_Flow() {
while (bfs()) {
for (int i = 1; i <= n; i++) {
//daca a fost vizitat si daca a ajuns la destinatie
if (vizitat[n + i] && v[n + i][2 * n + 1] > 0) {
flow = inf;
tata[2 * n + 1] = n + i;
//parcurgem lantul de la T la S si luam minimul(iP)
for (nod = 2 * n + 1; nod != 0; nod = tata[nod])
flow = min(flow, v[tata[nod]][nod]);
if (flow == 0)
continue;
//reglam flow-ul
for (nod = 2 * n + 1; nod != 0; nod = tata[nod]) {
v[tata[nod]][nod] -= flow;
v[nod][tata[nod]] += flow;
}
//adaugam iP ul la flow ul total
max_flow += flow;
}
}
}
}
int main() {
f >> n;
for (int i = 1; i <= n; i++) {
f >> out[i] >> in[i];
v[0][i] = out[i];
v[n + i][2 * n + 1] = in[i];
for (int j = 1; j <= n; j++)
if (i != j)
v[i][n + j] = 1;
}
reglare_Flow();
g <<max_flow<< '\n';
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++)
if (v[i][n + j] == 0 && i != j)
g << i << " " << j << '\n';
}
return 0;
}