Pagini recente » Cod sursa (job #3238063) | Cod sursa (job #2653402) | Cod sursa (job #2909491) | Cod sursa (job #2326859) | Cod sursa (job #407474)
Cod sursa(job #407474)
#include<stdio.h>
#include<string.h>
#define Nmx 101
int n,gri[Nmx],viz[Nmx],gre[Nmx];
int l[Nmx][Nmx],r[Nmx][Nmx];
void citire()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d%d",&gre[i],&gri[i]);
}
int pairup(int nod)
{
if(viz[nod])
return 0;
viz[nod]=1;
for(int i=1;i<=n;++i)
if(i!=nod&&r[i][0]<gri[i])
{
r[i][++r[i][0]]=nod;
l[nod][++l[nod][0]]=i;
return 1;
}
for(int i=1;i<=n;++i)
for(int j=1;j<=r[i][0];++j)
if(pairup(r[i][j]))
{
r[i][++r[i][0]]=nod;
l[nod][++l[nod][0]]=i;
return 1;
}
return 0;
}
void solve()
{
int cuplaj=0,ok=0;
do
{
ok=0;
memset(viz,0,sizeof(viz));
for(int i=1;i<=n;++i)
if(l[i][0]<gre[i]&&pairup(i))
{
cuplaj++;
ok=1;
}
}while(ok);
printf("%d\n",cuplaj);
for(int i=1;i<=n;++i)
for(int j=1;j<=l[i][0];++j)
printf("%d %d\n",i,l[i][j]);
}
int main()
{
freopen("harta.in","r",stdin);
freopen("harta.out","w",stdout);
citire();
solve();
return 0;
}