Cod sursa(job #237566)

Utilizator crawlerPuni Andrei Paul crawler Data 30 decembrie 2008 02:32:51
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <stdio.h>
#include <string.h>

#define Nmax 228

int c[Nmax][Nmax], f[Nmax][Nmax];
int q[Nmax], t[Nmax], v[Nmax],n;

int bfs()
{
    memset(t,0,sizeof(t));
    memset(v,0,sizeof(v));
    v[0] = 1;
    int st=0, dr=1, nod;
    q[1] = 0; 
    
    while(st<dr)
    {
        nod = q[++st];
        for (int i=1;i<=n;++i) if (v[i] == 0)
        if (f[nod][i] < c[nod][i])
        {
           v[i] = 1;           
           t[i] = nod;
           q[++dr] = i;              
        }
    }
    if (v[n] == 0) return 0;
    return 1;    
}

int main()
{
    freopen("harta.in","r",stdin);
    freopen("harta.out","w",stdout);
    
    scanf("%d", &n);
    
    int x,y, rec=n, tmp=0;
    
    for (int i=1;i<=n;++i)
    {
        scanf("%d%d", &x,&y);  
        c[0][i] = x;
        c[n+i][2*n+1] = y;
        for (int j=1;j<=n;++j) if (j != i) c[i][n+j] = 1; 
    }
 
    n = 2*n+1;
 

 
    while (bfs())
    {
          int add = 123456789;
          for (int nod = n;nod;nod=t[nod])
          if (c[t[nod]][nod]-f[t[nod]][nod] < add) add = c[t[nod]][nod]-f[t[nod]][nod];
          for (int nod = n;nod;nod=t[nod])
          {
              f[t[nod]][nod] += add;
              f[nod][t[nod]] -= add;
          }
          tmp += add;
    }

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

    for (int i=1;i<=rec;++i)
    for (int j=rec+1;j<=n;++j)
    if (f[i][j]) printf("%d %d\n",i,j-rec);
    
/*
    for (int i=0;i<=n;++i)
    for (int j=0;j<=n;++j)
    if (c[i][j]) printf("%d %d -> %d\n", i,j,c[i][j]);
*/
    
        

    return 0;
}