Cod sursa(job #4483)

Utilizator diaDiana Adrisor dia Data 4 ianuarie 2007 09:20:38
Problema Taramul Nicaieri Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.7 kb
#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;
        
}