Cod sursa(job #407696)

Utilizator jupanubv92Popescu Marius jupanubv92 Data 2 martie 2010 16:09:41
Problema Taramul Nicaieri Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include<stdio.h>
#define Nmx 202

int grde[Nmx],Q[Nmx*10],grdi[Nmx],i,prec[Nmx];
int C[Nmx][Nmx],s,N,n;

void citire()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
       scanf("%d%d",&grde[i],&grdi[i]);
    s=0;
    N=n+n+1;
}

void initi()
{
    for(int i=1;i<=n;++i)
    {
        C[s][i]=grde[i];
        C[i+n][N]=grdi[i];
    }
    for(int i=1;i<=n;++i)
        for(int j=n+1;j<N;++j)
            if(i!=j-n)
                C[i][j]=1;
}

int bfs()
{
    for (int i=1;i<=N;i++)
          prec[i]=-1;
     int st,dr=1;
     st=1;
     Q[1]=s;
     prec[s]=0;
     while(st<=dr)
     {
        int nod=Q[st];
        for (int i=1;i<=N;i++)
            if (C[nod][i] && prec[i]==-1)
               {
                    prec[i]=nod;
                    Q[++dr]=i;
               }
        ++st;
     }
     if(prec[N]!=-1)
        return 1;
    return 0;
}

void solve()
{
    int cpl=0;
    while(bfs())
    {
        for(int i=N;i!=s;i=prec[i])
        {
            C[prec[i]][i]--;
            C[i][prec[i]]++;
        }
        ++cpl;
    }
    printf("%d\n",cpl);
    for(int i=1;i<=n;++i)
        for(int j=n+1;j<N;++j)
            if(i!=j-n&&C[j][i])
                printf("%d %d\n",i,j-n);
}

int main()
{
    freopen("harta.in","r",stdin);
    freopen("harta.out","w",stdout);
    citire();
    initi();
    solve();
    return 0;
}