Cod sursa(job #3190024)

Utilizator dra_soloSolomon Dragos dra_solo Data 6 ianuarie 2024 20:14:52
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.13 kb
#include<stdio.h>
#include<vector>
#include<string.h>
#include<queue>
using namespace std;

#define NMAX 256
vector< int >G[NMAX];

int N,NODT;
int C[NMAX][NMAX];
int pred[NMAX+4];
bool bf()
{
    vector< int >::iterator it;
    memset(pred,-1,sizeof(pred));
    
    int nod;
    queue < int > Q;
    Q.push(0);
    
    while( !Q.empty() )
    {
           nod=Q.front();
           if( nod==NODT ) break;
           for(it=G[ nod ].begin(); it!=G[ nod ].end(); ++it)
           {
                     if( pred[*it]==-1 && C[nod][*it] > 0 )
                     {
                         Q.push(*it);
                         pred[*it]=nod;
                     }
           }
           Q.pop();
    }
    if( nod!=NODT ) return 1;
    
    for(nod=NODT; nod; nod=pred[nod])
    {
                  --C[pred[nod]][nod];
                  ++C[nod][pred[nod]];
    }
    
    return 0;
}

void show()
{
     int i,j;
     for(i=1; i<=N; ++i)
              for(j=1; j<=N; ++j)
                       if( i!=j && !C[i][j+N] )
                       {
                           printf("%d %d\n",i,j);
                       }
}

void solve()
{
     int ANS=0;
     
     while( !bf() )
            ++ANS;
            
     printf("%d\n",ANS);     
     show();
}

int main()
{
    freopen("harta.in","r",stdin);
    freopen("harta.out","w",stdout);
    
    scanf("%d",&N);
    NODT=(N<<1)+2;
    
    int i,j;
    int a1,a2;
    for(i=1; i<=N; ++i)
    {
             scanf("%d%d\n",&a1,&a2);
             
             G[i].push_back(0);
             G[0].push_back(i);
             C[0][i]=a1;
             
             G[i+N].push_back(NODT);
             G[NODT].push_back(i+N);
             C[i+N][NODT]=a2;
             
             for(j=1; j<=N; ++j)
             {
                      if( j!=i )
                      {
                          G[i].push_back( j+N );
                          G[j+N].push_back( i );
                          C[i][j+N]=1;C[j+N][i]=0;
                      }
             }
             
    }
    
    solve();    
    return 0;
}