Pagini recente » Cod sursa (job #2187802) | Cod sursa (job #720765) | Cod sursa (job #1828835) | Cod sursa (job #69345) | Cod sursa (job #407696)
Cod sursa(job #407696)
#include<stdio.h>
#define Nmx 202
int grde[Nmx],Q[Nmx*10],grdi[Nmx],i,prec[Nmx];
int C[Nmx][Nmx],s,N,n;
void citire()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d%d",&grde[i],&grdi[i]);
s=0;
N=n+n+1;
}
void initi()
{
for(int i=1;i<=n;++i)
{
C[s][i]=grde[i];
C[i+n][N]=grdi[i];
}
for(int i=1;i<=n;++i)
for(int j=n+1;j<N;++j)
if(i!=j-n)
C[i][j]=1;
}
int bfs()
{
for (int i=1;i<=N;i++)
prec[i]=-1;
int st,dr=1;
st=1;
Q[1]=s;
prec[s]=0;
while(st<=dr)
{
int nod=Q[st];
for (int i=1;i<=N;i++)
if (C[nod][i] && prec[i]==-1)
{
prec[i]=nod;
Q[++dr]=i;
}
++st;
}
if(prec[N]!=-1)
return 1;
return 0;
}
void solve()
{
int cpl=0;
while(bfs())
{
for(int i=N;i!=s;i=prec[i])
{
C[prec[i]][i]--;
C[i][prec[i]]++;
}
++cpl;
}
printf("%d\n",cpl);
for(int i=1;i<=n;++i)
for(int j=n+1;j<N;++j)
if(i!=j-n&&C[j][i])
printf("%d %d\n",i,j-n);
}
int main()
{
freopen("harta.in","r",stdin);
freopen("harta.out","w",stdout);
citire();
initi();
solve();
return 0;
}