Pagini recente » Cod sursa (job #321366) | Cod sursa (job #2843598) | Cod sursa (job #156525) | Cod sursa (job #787756) | Cod sursa (job #130746)
Cod sursa(job #130746)
#include <cstdio>
const int maxn = 204;
FILE *in = fopen("harta.in","r"), *out = fopen("harta.out","w");
int n;
int a[maxn][maxn], f[maxn][maxn], gin[maxn], gout[maxn];
int viz[maxn];
int q[maxn];
int g;
void readinit()
{
fscanf(in, "%d", &n);
g = 2*n + 1;
for ( int i = 1; i <= n; ++i )
{
fscanf(in, "%d %d", &gin[i], &gout[i]);
a[0][i] = gin[i];
a[n + i][g] = gout[i];
}
for ( int i = 1; i <= n; ++i )
for ( int j = 1; j <= n; ++j )
if ( i != j )
a[i][n + j] = 1;
}
int h;
int bf()
{
for ( int i = 0; i <= g; ++i )
viz[i] = -1;
int p = 0, u = 0;
q[p] = 0;
viz[p] = 0;
int x;
while ( p <= u )
{
x = q[p++];
for ( int i = 0; i <= g; ++i )
if ( f[x][i] < a[x][i] && viz[i] == -1 )
{
viz[i] = x, q[++u] = i;
if ( i == g )
return 1;
}
}
return 0;
}
void go()
{
while ( bf() )
{
++h;
for ( int i = g; i; i = viz[i] )
++f[ viz[i] ][i], --f[i][ viz[i] ];
}
}
int main()
{
readinit();
go();
fprintf(out, "%d\n", h);
for ( int i = 1; i <= n; ++i )
for ( int j = 1; j <= n; ++j )
if ( f[i][j + n] )
fprintf(out, "%d %d\n", i, j);
return 0;
}