Cod sursa(job #303733)

Utilizator Mishu91Andrei Misarca Mishu91 Data 10 aprilie 2009 11:53:55
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.99 kb
#include <cstdio>
#include <cstring>

#define MAX_N 205
#define INF 0x3f3f3f

int N, C[MAX_N][MAX_N], F[MAX_N][MAX_N], T[MAX_N];
int viz[MAX_N];
int S, D;

void citire()
{
    scanf("%d",&N);

    D = 2*N + 1;
    for(int i = 1; i <= N; ++i)
        scanf("%d %d",C[S]+i, C[i+N]+D);

    for(int i = 1; i <= N; ++i)
        for(int j = 1; j <= N; ++j)
            if(i != j) C[i][j + N] = 1;
}

inline int min(const int &a, const int &b)
{
    return ((a) < (b))? (a) : (b);
}

int BF()
{
    int Q[MAX_N];
    memset(viz, 0, sizeof viz);

    viz[S] = 1;
    Q[0] = 1;
    Q[1] = S;

    for(int i = 1; i <= Q[0]; ++i)
    {
        int nod = Q[i];
        if(nod == D) continue;

        for(int j = S; j <= D; ++j)
        {
            if(F[nod][j] == C[nod][j] || viz[j]) continue;

            viz[j] = 1;
            Q[++Q[0]] = j;
            T[j] = nod;
        }
    }
    S = 0;
    return viz[D];
}

void flux()
{
    int flow = 0, fmin;
    while(BF())
    {
        for(int k = N+1; k < D; ++k)
        {
            if(F[k][D] == C[k][D] || !viz[k]) continue;

            T[D] = k;
            fmin = INF;

            for(int i = D; i != S; i = T[i])
                fmin = min(fmin, C[T[i]][i] - F[T[i]][i]);

            for(int i = D; i != S; i = T[i])
                F[T[i]][i] += fmin,
                F[i][T[i]] -= fmin;

            flow += fmin;
        }

        #ifdef _HOME_
        for(int i = S; i <= D; ++i)
        {
            for(int j = S; j <= D; ++j)
                if(F[i][j] < 0)
                    fprintf(stderr,"%d ", F[i][j]);
                else
                    fprintf(stderr," %d ",F[i][j]);
            fprintf(stderr,"\n");
        }
        fprintf(stderr,"\n\n");
        #endif
    }

    printf("%d\n", flow);

    for(int i = 1; i <= N; ++i)
        for(int j = N+1; j < D; ++j)
            if(F[i][j] > 0)
                printf("%d %d\n",i, j - N);
}

int main()
{
    freopen("harta.in","rt",stdin);
    freopen("harta.out","wt",stdout);

    citire();
    flux();
}