Cod sursa(job #251826)
# include <cstdio>
# include <algorithm>
using namespace std;
# define FIN "harta.in"
# define FOUT "harta.out"
# define MAXN 105
int N, source, sink;
int T[MAXN];
int Stack[MAXN];
int C[MAXN][MAXN];
int BFS()
{
int i, j, vf;
Stack[vf = 1] = source;
memset(T, 0, sizeof(T));
for (i = 1; i <= vf; ++i)
for (j = 1; j <= sink; ++j)
if (!T[j] && C[Stack[i]][j])
{
T[j] = Stack[i];
Stack[++vf] = j;
if (j == sink) return 1;
}
return 0;
}
void flow()
{
int tflx = 0, i, j;
for (; BFS();)
{
for (int i = sink; i != source; i = T[i])
{
C[T[i]][i] --;
C[i][T[i]] ++;
}
tflx ++;
}
printf("%d\n",tflx);
for (i = 1; i <= N; ++i)
for (j = 1; j <= N; ++j)
if (C[j + N][i]) printf("%d %d\n",i, j);
}
int main()
{
freopen(FIN,"r",stdin);
freopen(FOUT,"w",stdout);
scanf("%d",&N);
source = 0; sink = 2 * N + 1;
for (int i = 1; i <= N; ++i)
{
int x, y;
scanf("%d%d",&x, &y);
C[source][i] = x;
C[i + N][sink] = y;
}
for (int i = 1; i <= N; ++i)
for (int j = 1; j <= N; ++j)
if (i != j) C[i][j + N] = 1;
flow();
return 0;
}