Cod sursa(job #35689)

Utilizator cromdioxidSasa Pastor cromdioxid Data 22 martie 2007 12:35:26
Problema Taramul Nicaieri Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.99 kb
#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 = 0; i <= D; 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 0 = sursa, 1...N noduri N+1...2*N alte noduri 2*N+1 dest
    S = 0;
    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); )
        for (i = 0; i <= D; i++)
        {
            if (!T[i] || C[i][D] <= F[i][D])
                continue;
            r = C[i][D] - F[i][D];
            for (j = i; j != S; j = T[j])
                r = min(r, C[T[j]][j] - F[T[j]][j]);
            if (r == 0)
                continue;
            F[i][D] += r;
            F[D][i] -= r;
            for (j=i; j !=S; j = T[j])
            {
                F[T[j]][j] += r;
                F[j][T[j]] -= r;
            }
            flux += 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;
}