Pagini recente » Cod sursa (job #1559961) | Cod sursa (job #2678643) | Cod sursa (job #1353878) | Cod sursa (job #641190) | Cod sursa (job #3188990)
#include <iostream>
#include <fstream>
#include <queue>
#include <string>
#include <vector>
#include <climits>
using namespace std;
class Graf {
vector<vector<int>> listeAdiacenta;
vector<vector<int>> flux;
vector<vector<int>> capacitate;
int bfs(const int& sursa, const int& destinatie, vector<int>& parinte) {
for (int i=0; i<parinte.size(); i++ ){
parinte[i] = -1;
}
parinte[sursa] = -2;
queue<pair<int, int>> q;
q.push({sursa, INT_MAX});
while (!q.empty()) {
int nodCurent = q.front().first;
int fluxCurent = q.front().second;
q.pop();
for (int vecin : listeAdiacenta[nodCurent]) {
if (parinte[vecin] == -1 && capacitate[nodCurent][vecin] > flux[nodCurent][vecin]) {
parinte[vecin] = nodCurent;
int fluxMinim = min(fluxCurent, capacitate[nodCurent][vecin] - flux[nodCurent][vecin]);
if (vecin == destinatie) {
return fluxMinim;
}
q.push({vecin, fluxMinim});
}
}
}
return 0;
}
public:
Graf(vector<vector<int>>& listeAdiacenta, vector<vector<int>>& capacitate) {
this->listeAdiacenta = listeAdiacenta;
this->capacitate = capacitate;
flux = vector<vector<int>>(capacitate.size(), vector<int>(capacitate.size(), 0));
}
int fluxMaxim(const int& sursa, const int& destinatie) {
vector<int> parinte(capacitate.size(), -1);
int fluxMaxim = 0;
while(true) {
int fluxGasit = bfs(sursa, destinatie, parinte);
if (!fluxGasit) {
break;
}
fluxMaxim += fluxGasit;
int nodCurent = destinatie;
while(nodCurent != sursa) {
int parinteNodCurent = parinte[nodCurent];
flux[parinteNodCurent][nodCurent] += fluxGasit;
flux[nodCurent][parinteNodCurent] -= fluxGasit;
nodCurent = parinteNodCurent;
}
}
return fluxMaxim;
}
vector<vector<int>> getFlux() {
return flux;
}
};
class Solutie {
public:
void Harta() {
ifstream f("harta.in");
ofstream g("harta.out");
int n, x, y;
f>>n;
vector<vector<int>> listeAdiacenta(n+n+2);
vector<vector<int>> capacitate(n+n+2, vector<int>(n+n+2, 0));
for (int i=1; i<=n; i++) {
f>>x>>y;
listeAdiacenta[0].push_back(i);
listeAdiacenta[i].push_back(0);
capacitate[0][i] = x;
listeAdiacenta[n+i].push_back(n+n+1);
listeAdiacenta[n+n+1].push_back(n+i);
capacitate[n+i][n+n+1] = y;
}
for (int i=1; i<=n; i++) {
for (int j=1; j<=n; j++) {
listeAdiacenta[i].push_back(n+j);
listeAdiacenta[n+j].push_back(i);
capacitate[i][n+j] = 1;
}
}
Graf graf(listeAdiacenta, capacitate);
int fluxMaxim = graf.fluxMaxim(0, n+n+1);
g<<fluxMaxim<<'\n';
for (int i=1; i<=n; i++) {
for (int j=n+1; j<=n+n; j++) {
if (graf.getFlux()[i][j])
g<<i<<' '<<j-n<<'\n';
}
}
}
};
int main() {
Solutie s;
s.Harta();
return 0;
}