Pagini recente » Cod sursa (job #1099645) | Cod sursa (job #3251083) | Cod sursa (job #2882785) | Cod sursa (job #1731551) | Cod sursa (job #3186168)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
ifstream intrare("harta.in");
ofstream iesire("harta.out");
struct Arc {
int capacitate, flux;
};
class Graf {
public:
Graf(int n);
void adaugaArc(int deLa, int catre, int capacitate);
int fluxMaxim(int sursa, int destinatie);
const vector<vector<Arc>>& getMatriceAdiacenta() const;
private:
vector<vector<Arc>> matriceAdiacenta;
vector<int> parinte;
bool bfs(int sursa, int destinatie);
};
Graf::Graf(int n) : matriceAdiacenta(2 * n + 2, vector<Arc>(2 * n + 2)), parinte(2 * n + 2) {}
void Graf::adaugaArc(int deLa, int catre, int capacitate) {
matriceAdiacenta[deLa][catre].capacitate += capacitate;
}
bool Graf::bfs(int sursa, int destinatie) {
fill(parinte.begin(), parinte.end(), -1);
queue<int> q;
q.push(sursa);
parinte[sursa] = sursa;
while (!q.empty()) {
int curent = q.front();
q.pop();
for (int urmator = 0; urmator < matriceAdiacenta.size(); ++urmator) {
if (parinte[urmator] == -1 && matriceAdiacenta[curent][urmator].capacitate - matriceAdiacenta[curent][urmator].flux > 0) {
q.push(urmator);
parinte[urmator] = curent;
}
}
}
return parinte[destinatie] != -1;
}
int Graf::fluxMaxim(int sursa, int destinatie) {
int fluxMaxim = 0;
while (bfs(sursa, destinatie)) {
int capacitateMinima = INT_MAX;
for (int curent = destinatie; curent != sursa; curent = parinte[curent]) {
int anterior = parinte[curent];
capacitateMinima = min(capacitateMinima,
matriceAdiacenta[anterior][curent].capacitate - matriceAdiacenta[anterior][curent].flux);
}
for (int curent = destinatie; curent != sursa; curent = parinte[curent]) {
int anterior = parinte[curent];
matriceAdiacenta[anterior][curent].flux += capacitateMinima;
matriceAdiacenta[curent][anterior].flux -= capacitateMinima;
}
fluxMaxim += capacitateMinima;
}
return fluxMaxim;
}
const vector<vector<Arc>>& Graf::getMatriceAdiacenta() const {
return matriceAdiacenta;
}
int main() {
int n;
intrare >> n;
Graf graf(2 * n + 2);
for (int i = 0; i < n; ++i) {
int x, y;
intrare >> x >> y;
graf.adaugaArc(2 * n, i, x);
graf.adaugaArc(n + i, 2 * n + 1, y);
for (int j = 0; j < n; ++j) {
if (i != j) {
graf.adaugaArc(i, n + j, 1);
}
}
}
int fluxMaxim = graf.fluxMaxim(2 * n, 2 * n + 1);
iesire << fluxMaxim << endl;
const vector<vector<Arc>>& matriceRezultat = graf.getMatriceAdiacenta();
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (matriceRezultat[i][n + j].flux == 1) {
iesire << i + 1 << ' ' << j + 1 << endl;
}
}
}
return 0;
}