Cod sursa(job #303733)
#include <cstdio>
#include <cstring>
#define MAX_N 205
#define INF 0x3f3f3f
int N, C[MAX_N][MAX_N], F[MAX_N][MAX_N], T[MAX_N];
int viz[MAX_N];
int S, D;
void citire()
{
scanf("%d",&N);
D = 2*N + 1;
for(int i = 1; i <= N; ++i)
scanf("%d %d",C[S]+i, C[i+N]+D);
for(int i = 1; i <= N; ++i)
for(int j = 1; j <= N; ++j)
if(i != j) C[i][j + N] = 1;
}
inline int min(const int &a, const int &b)
{
return ((a) < (b))? (a) : (b);
}
int BF()
{
int Q[MAX_N];
memset(viz, 0, sizeof viz);
viz[S] = 1;
Q[0] = 1;
Q[1] = S;
for(int i = 1; i <= Q[0]; ++i)
{
int nod = Q[i];
if(nod == D) continue;
for(int j = S; j <= D; ++j)
{
if(F[nod][j] == C[nod][j] || viz[j]) continue;
viz[j] = 1;
Q[++Q[0]] = j;
T[j] = nod;
}
}
S = 0;
return viz[D];
}
void flux()
{
int flow = 0, fmin;
while(BF())
{
for(int k = N+1; k < D; ++k)
{
if(F[k][D] == C[k][D] || !viz[k]) continue;
T[D] = k;
fmin = INF;
for(int i = D; i != S; i = T[i])
fmin = min(fmin, C[T[i]][i] - F[T[i]][i]);
for(int i = D; i != S; i = T[i])
F[T[i]][i] += fmin,
F[i][T[i]] -= fmin;
flow += fmin;
}
#ifdef _HOME_
for(int i = S; i <= D; ++i)
{
for(int j = S; j <= D; ++j)
if(F[i][j] < 0)
fprintf(stderr,"%d ", F[i][j]);
else
fprintf(stderr," %d ",F[i][j]);
fprintf(stderr,"\n");
}
fprintf(stderr,"\n\n");
#endif
}
printf("%d\n", flow);
for(int i = 1; i <= N; ++i)
for(int j = N+1; j < D; ++j)
if(F[i][j] > 0)
printf("%d %d\n",i, j - N);
}
int main()
{
freopen("harta.in","rt",stdin);
freopen("harta.out","wt",stdout);
citire();
flux();
}