Pagini recente » Cod sursa (job #1406846) | Cod sursa (job #2064381) | Cod sursa (job #3189343) | Cod sursa (job #2197065) | Cod sursa (job #222630)
Cod sursa(job #222630)
#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;
}