Pagini recente » Cod sursa (job #1879096) | Cod sursa (job #1940967) | Cod sursa (job #808632) | Cod sursa (job #1600430) | Cod sursa (job #184821)
Cod sursa(job #184821)
#include<cstdio>
#include<cstring>
int a[202][202],f[202][202],T[202],l[300],i,n,m,x,y,j;
inline int bf()
{
int st=0,dr=0;
l[0]=0;
memset(T,0,sizeof(T));
while(st<=dr)
{
x=l[st];
for(i=1;i<=2*n+1;i++)
if(a[x][i]-f[x][i]>0 && !T[i])
{
T[i]=x;
l[++dr]=i;
if(i==2*n+1) return 1;
}
++st;
}
return 0;
}
inline void flux()
{
while(bf())
{
x=2*n+1;
while(x!=0)
{
f[T[x]][x]++;
f[x][T[x]]--;
x=T[x];
}
}
for(i=1;i<=n;i++)
for(j=n+1;j<=2*n;j++)
if(i!=j-n && f[i][j]==1)
printf("%d %d\n",i,j-n);
}
int main()
{
freopen("harta.in","r",stdin);
freopen("harta.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d %d",&x,&y);
a[0][i]=x;
a[n+i][2*n+1]=y;
m+=x;
}
printf("%d\n",m);
for(i=1;i<=n;i++)
for(j=n+1;j<=2*n;j++)
if(i!=j-n)
a[i][j]=1;
flux();
fclose(stdout);
return 0;
}