Cod sursa(job #447325)

Utilizator Bogdan_CCebere Bogdan Bogdan_C Data 28 aprilie 2010 14:00:15
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 kb
#include<stdio.h>
#include<stdlib.h>
#include<vector>
#define FIN "harta.in"
#define FOUT "harta.out"
#define NMAX 204

using namespace std;
int source,sink;
vector< int > G[NMAX];
int N,M,c,x,y,viz[NMAX],coada[NMAX],F[NMAX][NMAX],RT[NMAX],fmax,fmin,C[NMAX][NMAX],flux;

int BF()
{
    memset(viz,0,sizeof(viz));
    int p,q;
    coada[p = q = 1] = source;
    viz[source] = 1;
    while( p <= q )
     {
            int nod = coada[p++];
            vector< int >::iterator it;
            for(it = G[nod].begin() ; it != G[nod].end() ; it++)
             {
                 if(  !C[nod][ *it ] || viz[ *it ]) continue;
                 viz [ *it ] = 1;
                 RT[ *it ]=nod;
                 coada[ ++q ] = *it;
                 if(*it==sink) {return 1;}
                   
            }
    }
    
    return 0;;
    }


int main()
{
    freopen(FIN,"r",stdin);
    freopen(FOUT,"w",stdout);
    scanf("%d\n",&N);
    source=0;
    sink=2*N+1;
    for(int i = 1 ; i <= N ; i++)
      {
            scanf("%d %d",&x,&y);
            C[source][i] = x;
            C[i+N][sink] = y; 
            G[source].push_back(i);
            G[i].push_back(0);
            G[i+N].push_back(2*N+1);
            G[sink].push_back(i+N);
        }
     for(int i=1;i<=N;i++)
      for(int j=N+1;j<sink ; j++)
       { C[i][j]=1;
        G[i].push_back(j);
        G[j].push_back(i);
            }   
      for(int i=1;i<=N;i++) C[i][i+N]=0;      
      for( ; BF() ; )
      {
         
        for( int nod =  sink ;nod!=source ; nod=RT[nod])
        {
        C[RT[nod]][nod] -= 1;
        C[nod][RT[nod]] += 1;     
        }
        flux += 1;
        }  
      
    printf("%d\n",flux);
    for(int i=1;i<=N;i++)
     for(int j=N+1;j<=2*N;j++)
      if(!C[i][j] && j!=i+N ) printf("%d %d\n",i,j-N); 
   
     return 0;   
    }