Pagini recente » Cod sursa (job #841912) | Cod sursa (job #1923910) | Cod sursa (job #3267478) | Cod sursa (job #662203) | Cod sursa (job #3188874)
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
//sursa = 0; nodurile_out = 1..n, nodurile_in = n+1..2n, dest = ultimu(2n+1);
int capacitate[204][204], n, suma_oprire;
vector<vector<int>> adj(100);
int drum_crestere(vector<int>&parent){
parent = vector<int>(2*n+2, -1);
queue<int>q;
int nod_curent;
q.push(0);
while(!q.empty()){
nod_curent = q.front();
q.pop();
for(int i = 2*n+1; i > 0; i--){
if(parent[i] == -1 && capacitate[nod_curent][i] > 0){
parent[i] = nod_curent;
if(i == 2*n+1){
return 1;
}
q.push(i);
}
}
}
return 0;
}
void fluxmax(){
int flux = 0;
vector<int>parent(2*n+1);
while(flux != suma_oprire){
flux += drum_crestere(parent);
int curent = 2*n+1, precedent;
while(curent != 0){
precedent = parent[curent]; // Cum ar veni
capacitate[precedent][curent] -= 1; // din prev am dat una catre curent si fluxu e mai mic
capacitate[curent][precedent] += 1; // si acum curent poate intoarce cu 1 mai mult in prev
curent = precedent;
}
}
}
int main()
{
int i, j;
fin>>n;
for(i = 1; i <= n; i++){
fin>>capacitate[0][i]>>capacitate[n+i][2*n+1];
suma_oprire += capacitate[0][i];
}
for(i = 1; i <= n; i++){
for(j = n+1; j <= 2*n; j++){
if(i != j - n){
capacitate[i][j] = 1;
}
}
}
fluxmax();
fout<<suma_oprire<<'\n';
for(i = n+1; i <= 2*n; i++){
for(j = 1; j <= n; j++){
if(capacitate[i][j] == 1){
fout<<j<<' '<<i-n<<'\n';
}
}
}
return 0;
}