Pagini recente » Rating Dumitra Andrei 322CC (dumandga) | Cod sursa (job #1256448) | Cod sursa (job #1918690) | Cod sursa (job #674942) | Cod sursa (job #36299)
Cod sursa(job #36299)
#include <stdio.h>
#include <string.h>
#define NMAX 220
#define INF 2000000
int T[NMAX], C[NMAX][NMAX], F[NMAX][NMAX], N, I[NMAX], O[NMAX], S, D;
int min(int a, int b)
{
return (a > b ? b : a);
}
int BF(int s, int d)
{
int q[NMAX], p, u, i, nod;
memset(T, 0, sizeof(T));
for (p = u = 0, q[0] = s, T[s] = -1; p <= u; p++)
{
nod = q[p];
for (i = 1; i <= 2 * N + 2; i++)
if (!T[i] && C[nod][i] > F[nod][i])
{
q[++u] = i;
T[i] = nod;
if (i == d) return 1;
}
}
return 0;
}
int main()
{
int i, j, flux, r;
freopen("harta.in", "rt", stdin);
freopen("harta.out", "wt", stdout);
scanf("%d", &N);
for (i = 1; i <= N; i++)
scanf("%d %d", &I[i], &O[i]);
// construire graf 2*N+2 = sursa, 1...N noduri N+1...2*N alte noduri 2*N+1 dest
S = 2 * N + 2;
D = 2 * N + 1;
for (i = 1; i <= N; i++)
{
C[S][i] = I[i];
C[N+i][D] = O[i];
}
for (i = 1; i <= N; i++)
for (j = N + 1; j <= 2 * N; j++)
if (i != j - N)
C[i][j] = 1;
//flux
for (flux = 0; BF(S, D); flux += r)
{
r = INF;
for (i = D; i != S; i = T[i])
r = min(r, C[T[i]][i] - F[T[i]][i]);
for (i = D; i != S; i = T[i])
{
F[T[i]][i] += r;
F[i][T[i]] -= r;
}
}
printf("%d\n", flux);
for (i = 1; i <= N; i++)
for (j = N + 1; j <= 2 * N; j++)
{
if (F[i][j] > 0)
printf("%d %d\n", i, j - N);
if (F[j][i] > 0)
printf("%d %d\n", j - N, i);
}
return 0;
}