Pagini recente » Cod sursa (job #2812107) | Cod sursa (job #1992229) | Cod sursa (job #978108) | Cod sursa (job #715365) | Cod sursa (job #2961210)
#include<iostream>
#include<fstream>
#include<queue>
using namespace std;
#define Max 1000
int N, x, y, maxflow, sum;
int graf_rez[Max][Max];
bool vizitat[Max];
int tata[Max];
void citesteDate();
void scrieRezultat();
bool lantBFS(){
// initializare date
for(int i = 0; i <= 2*N+1; i++){
vizitat[i] = 0, tata[i] = -1;
}
queue<int> coada;
coada.push(0); // nodul de start
vizitat[0] = 1;
while(!coada.empty()){
int curent = coada.front();
coada.pop();
vizitat[curent] = 1;
if(curent == 2*N+1) return true;
for(int nod = 1; nod <= 2*N+1; nod ++){
if(!vizitat[nod] && graf_rez[curent][nod] > 0){
tata[nod] = curent;
coada.push(nod);
}
}
}
return false;
}
int main(){
citesteDate();
// cat timp se poate construi un lant minim
while(lantBFS()){
// pornim verificarea tuturor lanturilor gasite de la nodurile tata ale nodului final
for(int nod = 1; nod <= 2*N; nod ++){
if(vizitat[nod] && graf_rez[nod][2*N+1] > 0) // valoare pozitiva => muchia nu este saturata
{
// aflam valoarea minima a fluxului in cadrul lantului curent
int flux_curent = graf_rez[nod][2*N+1];
// actualizam tatal nodului final in functie de lantul curent gasit
tata[2*N+1] = nod;
int auxiliar = nod;
while(tata[auxiliar] != -1){
flux_curent = min(flux_curent, graf_rez[tata[auxiliar]][auxiliar]);
auxiliar = tata[auxiliar];
}
if(flux_curent > 0){
auxiliar = 2*N+1;
while(tata[auxiliar] != -1){
graf_rez[ tata[auxiliar] ][ auxiliar ] -= flux_curent;
graf_rez[ auxiliar ][ tata[auxiliar] ] += flux_curent;
auxiliar = tata[auxiliar];
}
// actualizam fluxul maxim
maxflow += flux_curent;
}
}
}
}
scrieRezultat();
return 0;
}
void citesteDate(){
ifstream f("harta.in");
f>>N;
for(int i=1; i<=N; i++){
f>>x>>y;
graf_rez[0][i] = x;
graf_rez[N+i][2*N+1] = y;
}
// initializare date
for(int i=1; i<=N; i++)
for(int j=1; j<=N; j++)
if(j!=i)
graf_rez[i][N+j] = 1;
}
void scrieRezultat(){
ofstream g("harta.out");
g<<maxflow<<"\n";
for(int i=1; i<=N; i++)
for(int j=1; j<=N; j++)
if(i != j && graf_rez[N+j][i])
g<<i<<" "<<j<<"\n";
}