Pagini recente » Cod sursa (job #2945189) | Cod sursa (job #1802854) | Cod sursa (job #247931) | Cod sursa (job #25540) | Cod sursa (job #143820)
Cod sursa(job #143820)
#include <stdio.h>
#define NMax 101
int n, nr;
int intrare[NMax], iesire[NMax];
int flux[NMax][NMax], C[NMax*2], prec[NMax*2], fin[NMax], fout[NMax], in, sf;
void citire();
void rez();
void afis();
int main()
{
citire();
rez();
afis();
return 0;
}
void afis()
{
int i, j;
printf( "%d\n", nr - 1);
for (i=1; i<=n; i++)
for (j=n+1; j<=n*2; j++)
if ( flux[i][j-n] )
printf( "%d %d\n", i, j-n );
}
void rez()
{
int i, j, aux;
while ( 1 )
{
nr++;
in = sf = 0;
// bfs din sursa
for (i=1; i<=n; i++)
{
prec[i] = prec[i+n] = -1;
if ( fin[i] < iesire[i] )
{
prec[i] = 0;
C[sf++] = i;
}
}
// bfs din noduri 1..2n
while ( in <= sf )
{
aux = C[in++];
// stanga
if ( aux <= n )
{
for (i=n+1; i<=n*2; i++)
if ( !flux[aux][i-n] && aux != i-n && prec[i] == -1 )
{
C[sf++] = i;
prec[i] = aux;
}
}
// dreapta
else
{
for (i=1; i<=n; i++ )
if ( flux[i][aux-n] && i != aux-n && prec[i] == -1 )
{
C[sf++] = i;
prec[i] = aux;
}
}
}
aux = 0;
// bfs spre destinatie
for (i=n+1; i<=n*2; i++)
if ( prec[i] != -1 && fout[i-n] < intrare[i-n] )
{
aux = i;
break;
}
if ( aux == 0 )
break;
fout[aux - n]++;
while ( prec[aux] != 0 )
{
if ( aux <= n )
flux[aux][prec[aux]-n]--;
else
flux[prec[aux]][aux-n]++;
aux = prec[aux];
}
fin[aux]++;
}
}
void citire()
{
int i;
freopen( "harta.in", "rt", stdin );
freopen( "harta.out", "wt", stdout );
scanf( "%d", &n );
for (i=1; i<=n; i++)
scanf( "%d %d", &intrare[i], &iesire[i] );
}