Pagini recente » Cod sursa (job #2629912) | Cod sursa (job #2476382) | Cod sursa (job #1610157) | Cod sursa (job #1202037) | Cod sursa (job #2962189)
#include <fstream>
#include <queue>
#include <cmath>
#define N 250 /// 2 * n + 1 e maxim
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
int flux[N][N], viz[N], tata[N], out, in;
vector <int> l[N]; /// lista de muchii
vector <int> li[N]; /// lista de muchii intoarcere
int n, m;
queue<int> c;
int S, T;
int sol_flux;
void Citire()
{
fin >> n; /// nr de noduri
S = 0;
T = 2*n + 1;
/// pt fiecare nod ni se spune cate muchii pleaca si intra
for(int i = 1; i <= n; i++)
{
fin >> out >> in;
/// dublam nodurile ca sa legam fiecare cu fiecare
flux[S][i] = out;
flux[n+i][T] = in;
for(int j = 1; j <= n; j++)
if( i != j)
flux[i][n+j] = 1;
}
}
int Constr_Lant_Nesat_BF()
{
int vecin;
for(int i=0; i<=2*n+1; i++)
{
tata[i] = 0;
viz[i] = 0;
}
c.push(S);
viz[S] = 1;
tata[S] = -1;
int nod;
while(c.empty() == 0)
{
nod = c.front();
c.pop();
if(nod == T)
return 1;
for(int i = 1; i <= T; i++)
if( flux[nod][i] > 0 && viz[i] == 0)
{
c.push(i);
viz[i] = 1;
tata[i] = nod;
}
}
return 0;
}
void Reviz_Flux_Lant()
{
/// plecam in sens invers, de la T -> S
for(int i=1; i<=n; i++)
if(flux[n+i][T] > 0 && viz[n+i] == 1)
{
tata[T] = n + i;
int flux_min = N*N;
int nod = T;
while(nod != S) /// cat timp nodul actual nu e nodul de unde am inceput
{
int parent = tata[nod];
flux_min = min(flux_min, flux[parent][nod]);
nod = parent;
}
if (flux_min == 0) continue;
nod = T;
while(nod != S)
{
int parent = tata[nod];
flux[parent][nod] = flux[parent][nod] - flux_min;
flux[nod][parent] = flux[nod][parent] + flux_min;
nod = parent;
}
sol_flux = sol_flux + flux_min;
}
}
void Implementare()
{
while(Constr_Lant_Nesat_BF())
Reviz_Flux_Lant();
fout << sol_flux <<"\n";
for(int i = 1; i<=n; i++)
for(int j = 1; j<=n; j++)
if(i!=j && flux[i][n+j] == 0)
fout << i <<" "<< j <<"\n";
}
int main()
{
Citire();
Implementare();
/* Reviz_Flux_Lant();
fout << Constr_Lant_Nesat_BF() <<"\n";
fout << sol_flux;*/
return 0;
}