Pagini recente » Cod sursa (job #1819220) | Cod sursa (job #1875841) | Cod sursa (job #1429114) | Cod sursa (job #2895806) | Cod sursa (job #4483)
Cod sursa(job #4483)
#include <stdio.h>
#define NMAX 211
#define QMAX (1<<8)
int A[NMAX][NMAX], Gi[NMAX], Go[NMAX];
int N, Flow, Q[QMAX], Cup[NMAX];
int eflux()
{
int i, hi, lo, nod;
for (i = 0; i < NMAX; i++)
Q[i] = 0, Cup[i] = -1;
Q[0] = 0; Cup[0] = 0;
for (lo = 0, hi = 1; lo != hi; lo = (lo+1)&(QMAX-1))
{
nod = Q[lo];
for (i = 0; i < 2*N+2; i++)
if (A[nod][i] && Cup[i] == -1)
{
Cup[i] = nod;
Q[hi] = i;
hi = (hi+1)&(QMAX-1);
if (i == 2*N+1) { Flow++; return 1; }
}
}
return 0;
}
int main()
{
int i, j, indeg = 0, outdeg = 0;
freopen("harta.in", "r", stdin);
freopen("harta.out", "w", stdout);
scanf("%d", &N);
for (i = 1; i <= N; i++)
scanf("%d %d", Gi+i, Go+i), indeg += Gi[i], outdeg += Go[i],
A[0][i] = Gi[i], A[i+N][2*N+1] = Go[i];
for (i = 1; i <= N; i++)
for (j = 1; j <= N; j++)
if (i != j) A[i][N+j] = 1;
if (indeg != outdeg) { printf("-1\n"); return 0; }
while (eflux())
for (i = 2*N+1; i; i = Cup[i])
A[i][Cup[i]]++, A[Cup[i]][i]--;
if (Flow < indeg) { printf("-1\n"); return 0; }
else
{
printf("%d\n", Flow);
for (i = 1; i <= N; i++)
for (j = 1; j <= N; j++)
if (A[j+N][i]) printf("%d %d\n", i, j);
}
return 0;
}