Pagini recente » concurs_pd | Cod sursa (job #2109964) | Cod sursa (job #590943) | Arhiva de probleme | Cod sursa (job #222608)
Cod sursa(job #222608)
#include<stdio.h>
#include<vector>
#include<string.h>
using namespace std;
#define NMAX 128
#define mult 16384
vector< int >G[NMAX];
int Q[mult];
int pred[NMAX*2+4];
int N,NODT;
int C[NMAX][NMAX];
bool viz[mult];
bool bf()
{
vector< int >::iterator it;
memset(viz,0,sizeof(viz));
int inc=1,sf=1,nod;
while( inc<=sf )
{
nod=Q[inc++];
viz[nod]=1;
if( nod==NODT ) break;
for(it=G[ nod ].begin(); it!=G[ nod ].end(); ++it)
{
if( !viz[*it] && C[nod][*it] > 0 )
{
Q[++sf]=*it;
pred[*it]=nod;
}
}
}
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",j,i);
}
}
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",&a2,&a1);
G[i].push_back(0);
G[0].push_back(i);
C[i][0]=C[0][i]=a1;
G[i+N].push_back(NODT);
G[NODT].push_back(i+N);
C[i+N][NODT]=C[NODT][i+N]=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]=C[j+N][i]=1;
}
}
}
solve();
return 0;
}