Pagini recente » Cod sursa (job #353336) | Cod sursa (job #2267495) | Cod sursa (job #61392) | Cod sursa (job #2803491) | Cod sursa (job #2961140)
#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
int n;
vector<vector<int>> lista(305);
int cap[205][205];
int cap_init[205][205];
int viz[205], tata[205];//ca sa retin nodurile vizitate si tatal nodurilor pentru reconstruirea drumului
int bfs(){//bfs pentru aflarea existentei drumului de crestere
queue<int> coada;
coada.push(0);
for(int i = 0; i <= 2*n+1; i++){
tata[i] = -1;
viz[i] = 0;
}
viz[0]++;
while(coada.size()!=0){
int nod_cur = coada.front();
cout<<nod_cur<<" "<<tata[nod_cur]<<endl;
if(nod_cur == 2*n+1)//daca am ajuns la final inseamna ca am gasit un drum de crestere
return 1;
for(int i = 0; i < lista[nod_cur].size(); i++){
int nod_vec = lista[nod_cur][i];
if(cap[nod_cur][nod_vec] > 0 && viz[nod_vec] == 0){//daca am gasit un nod prin care nu am mai fost care mai are loc, trecem prin el
viz[nod_vec]++;
tata[nod_vec] = nod_cur;
coada.push(nod_vec);
}
}
coada.pop();//scot din coada nodul prin care deja am trecut
}
return 0;//nu am gasit
}
int Edmonds_Karp(){
int max_flux = 0;//fluxul maixim
while(bfs()){//cat timp avem drum de crestere
for(int i = 0; i < lista[2*n+1].size(); i++){
int nod_cur = lista[2*n+1][i];
if(cap[nod_cur][2*n+1] > 0 && viz[nod_cur]){//daca este drum care a dus de la vecinul lui n la n care mai are capacitate
//si a fost vizitat in verificarea noastra, atunci reconstituim drumul parcurs
//cout<<nod_cur<<" ";
vector<int> drum;//reconstituirea drumului
drum.push_back(nod_cur);
while(tata[nod_cur]!=-1){
nod_cur = tata[nod_cur];
drum.push_back(nod_cur);
}
int minim = 9999999;//bottleneckul nostru
for(int i = 0; i < drum.size(); i++)//vedem care este bottleneckul drumului
if(i == 0)
minim = min(minim, cap[drum[i]][2*n+1]);
else
minim = min(minim, cap[drum[i]][drum[i-1]]);
max_flux += minim;//il adaugam la flux doarece e cea mai mare valoare pe care o putem trece prin acel drum
for(int i = 0; i < drum.size(); i++){
if(i == 0){
cap[drum[i]][2*n+1] -= minim;//scadem cap de la muchia de crestere
cap[2*n+1][drum[i]] +=minim;//dar crestem cap muchiei de intoarece
}
else{
cap[drum[i]][drum[i-1]] -= minim;
cap[drum[i-1]][drum[i]] += minim;
}
}
//cout<<minim<<" ";
}
}
for(int i = 0; i <= 2*n+1; i++){
for(int j = 0; j <= 2*n+1; j++)
cout<<cap[i][j]<<" ";
cout<<endl;
}
cout<<endl;
}
return max_flux;//fluxul maxim
}
int main()
{
fin>>n;
for(int i = 1; i <= n; i++){
int x, y;
fin>>x>>y;
lista[0].push_back(i);
lista[1].push_back(0);
cap[0][i] = x;
cap_init[0][i] = x;
lista[n+i].push_back(2*n+1);
lista[2*n+1].push_back(n+i);
cap[n+i][2*n+1] = y;
cap_init[n+i][2*n+1] = y;
}
for(int i = 1; i <= n; i++)
for(int j = n+1; j < 2*n+1; j++){
if((i+n)!=j){
lista[i].push_back(j);
lista[j].push_back(i);
cap[i][j] = 1;
cap_init[i][j] = 1;
}
}
// for(int i = 0; i <= 2*n+1; i++){
// for(int j = 0; j <= 2*n+1; j++)
// cout<<cap[i][j]<<" ";
// cout<<endl;
// }
// cout<<endl;
fout<<Edmonds_Karp()<<"\n";
for(int i = 1; i <= n; i++)
for(int j = n+1; j < 2*n+1; j++)
if(cap_init[i][j] == 1 && cap[i][j] == 0)
fout<<i<<" "<<j-n<<"\n";
}