Pagini recente » Cod sursa (job #2117748) | Cod sursa (job #2956833)
#include <bits/stdc++.h>
#define dim 220
#define inf INT_MAX
using namespace std;
ifstream f("harta.in");
ofstream o("harta.out");
int tata[dim], a[dim][dim], in[dim], out[dim], n, m, nod, flow, maxFlow;
bool viz[dim];
//algoritmul clasic de bfs pt max flow doar ca in loc de t am 2n+1
bool bfs() {
queue<int> coada;
memset(tata, 0, sizeof(tata));
memset(viz, false, sizeof(viz));
coada.push(0);
viz[0] = true;
tata[0] = -1;
while (!coada.empty()) {
int front = coada.front();
coada.pop();
if (front == 2 * n + 1)
return true;
for (int i = 1; i <= 2 * n + 1; i++) {
if (!viz[i] && a[front][i] > 0) {
coada.push(i);
viz[i] = true;
tata[i] = front;
}
}
}
return false;
}
void citireDate() {
f >> n;
for (int i = 1; i <= n; i++) {
f >> out[i] >> in[i];
//Adaugam un nou start si un nou final(cu muchii de
// capacitati egale cu gradele out, respectiv in),
//si dublam nodurile, ca sa l putem lega pe fiecare cu fiecare
//2n+1 fiind t-ul
a[0][i] = out[i];
a[n + i][2 * n + 1] = in[i];
for (int j = 1; j <= n; j++)
if (i != j)
a[i][n + j] = 1;
}
}
void reglamFlow() {
while (bfs()) {
for (int i = 1; i <= n; i++) {
//daca a fost vizitat si daca a ajuns la destinatie
if (viz[n + i] && a[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, a[tata[nod]][nod]);
if (flow == 0)
continue;
//reglam flow-ul
for (nod = 2 * n + 1; nod != 0; nod = tata[nod]) {
a[tata[nod]][nod] -= flow;
a[nod][tata[nod]] += flow;
}
//adaugam iP ul la flow ul total
maxFlow += flow;
}
}
}
}
void afisareDate() {
o << maxFlow << '\n';
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++)
if (a[i][n + j] == 0 && i != j)
o << i << " " << j << '\n';
}
}
int main() {
citireDate();
reglamFlow();
afisareDate();
return 0;
}