Pagini recente » Cod sursa (job #1990992) | Cod sursa (job #2703969) | Politia | Cod sursa (job #1299840) | Cod sursa (job #159675)
Cod sursa(job #159675)
#include <fstream>
#define NMax 202
#define min(a,b) ( (a)<(b)?(a):(b) )
#define abs(x) ( (x)>0?(x):(-x) )
using namespace std;
int C[NMax][NMax], F[NMax][NMax];
int v[NMax], Q[NMax];
int n;
void citire()
{
int i;
ifstream fin("harta.in");
fin >> n;
for( i=1; i<=n; i++ )
fin >> C[n+i][2*n+1] >> C[0][i];
fin.close();
}
void init()
{
int i, j;
for( i=1; i<=n; i++ )
for( j=1; j<=n; j++ )
if( i!=j )
C[i][n+j]=1;
}
int bfs()
{
int st, dr, i, x;
Q[0]=0; st=dr=0; v[0]=1;
while( st<=dr && !v[2*n+1] )
{
x = Q[st++];
for( i=1; i<=2*n+1; i++ )
if( !v[i] )
if( F[x][i] < C[x][i] )
{
v[i]=x;
Q[++dr]=i;
}
else if( F[i][x] > 0 )
{
v[i]=-x;
Q[++dr]=i;
}
}
return !v[2*n+1];
}
void ek()
{
int i, a, b, flux, lg;
int L[NMax];
do
{
for( i=0; i<=2*n+1; i++ ) v[i]=0;
if( bfs() ) return;
L[0] = 2*n+1; lg=0;
a = b = 200;
while( L[lg]!=0 )
{
++lg;
L[lg] = abs( v[L[lg-1]] );
if( v[L[lg-1]] > 0 )
a = min( a, C[L[lg]][L[lg-1]] - F[L[lg]][L[lg-1]] );
else if( v[L[lg-1]] < 0 )
b = min( b, F[L[lg-1]][L[lg]] );
}
flux = min( a, b );
for( i=lg; i>0; i-- )
if( v[L[i-1]]>0 )
F[L[i]][L[i-1]]+=flux;
else
F[L[i-1]][L[i]]-=flux;
}
while( 1 );
}
void afisare()
{
int i, j;
ofstream fout("harta.out");
int nrm=0;
for( i=1; i<=n; i++ )
nrm+=F[n+i][2*n+1];
fout << nrm << '\n';
for( i=1; i<=n; i++ )
for( j=1; j<=n; j++ )
if( F[i][n+j] )
fout << i << ' ' << j << '\n';
fout.close();
}
int main()
{
citire();
init();
ek();
afisare();
return 0;
}