Pagini recente » Cod sursa (job #1363211) | Cod sursa (job #421518) | Cod sursa (job #346014) | Cod sursa (job #2659609) | Cod sursa (job #3189816)
#include <fstream>
#include <vector>
#include <queue>
std::ifstream fin("harta.in");
std::ofstream fout("harta.out");
class Graf {
int numarNoduri;
std::vector<std::vector<int>> listaAdiacenta;
std::vector<std::vector<int>> capacitati;
std::vector<std::vector<int>> flux;
public:
explicit Graf(int numarNoduri) : numarNoduri(numarNoduri) {
listaAdiacenta.resize(numarNoduri);
capacitati.resize(numarNoduri);
for(int i = 0; i < numarNoduri; i++)
capacitati[i].resize(numarNoduri, 0);
flux.resize(numarNoduri);
for(int i = 0; i < numarNoduri; i++)
flux[i].resize(numarNoduri, 0);
}
void adaugaCapacitate(int x, int y, int capacitate) {
listaAdiacenta[x].push_back(y);
listaAdiacenta[y].push_back(x);
capacitati[x][y] = capacitate;
}
bool bfsForFlux(std::vector<int>& tati) {
std::queue<int> coada;
std::vector<int> vizitati(numarNoduri, 0);
int sursa = numarNoduri - 2;
int destinatie = numarNoduri - 1;
coada.push(sursa);
vizitati[sursa] = 1;
while (!coada.empty()) {
int nod = coada.front();
coada.pop();
for (int i = 0; i < listaAdiacenta[nod].size(); i++) {
int vecin = listaAdiacenta[nod][i];
if (vizitati[vecin] == 0 && (capacitati[nod][vecin] - flux[nod][vecin] > 0)) {
coada.push(vecin);
tati[vecin] = nod;
vizitati[vecin] = 1;
}
}
}
return vizitati[destinatie];
}
int fluxMaxim() {
int fluxMaxim = 0;
int destinatie = numarNoduri - 1;
int sursa = numarNoduri - 2;
std::vector<int> tati(numarNoduri, -1);
while (bfsForFlux(tati)) {
int capacitateMinima = INT_MAX;
int nod = destinatie;
while (nod != sursa) {
capacitateMinima = std::min(capacitati[tati[nod]][nod] - flux[tati[nod]][nod], capacitateMinima);
nod = tati[nod];
}
fluxMaxim += capacitateMinima;
nod = destinatie;
while (nod != sursa) {
flux[tati[nod]][nod] += capacitateMinima;
flux[nod][tati[nod]] -= capacitateMinima;
nod = tati[nod];
}
for (int i = 0; i < numarNoduri; i++) {
tati[i] = -1;
}
}
return fluxMaxim;
}
std::vector<std::vector<int>> getFlux() const {
return flux;
}
};
int main() {
int numarNoduri, x, y;
fin >> numarNoduri;
Graf g(2 * numarNoduri + 2);
for (int i = 0; i < numarNoduri; i++) {
fin >> x >> y;
g.adaugaCapacitate(2 * numarNoduri, i, x);
g.adaugaCapacitate(i + numarNoduri, 2 * numarNoduri + 1, y);
for (int j = 0; j < numarNoduri; j++) {
if (i != j)
g.adaugaCapacitate(i, j + numarNoduri, 1);
}
}
fin.close();
fout << g.fluxMaxim() << '\n';
std::vector<std::vector<int>> rez = g.getFlux();
for (int i = 0; i < numarNoduri; i++) {
for (int j = 0; j < numarNoduri; j++) {
if (rez[i][j + numarNoduri] == 1)
fout << i + 1 << ' ' << j + 1 << '\n';
}
}
fout.close();
return 0;
}