Pagini recente » Cod sursa (job #2059705) | Cod sursa (job #1314792) | Cod sursa (job #481374) | Cod sursa (job #2785255) | Cod sursa (job #42250)
Cod sursa(job #42250)
#include<stdio.h>
#define Nm 101
#define Inf Nm*Nm
#define min(a,b) ((a)<(b)?(a):(b))
int C[2*Nm][2*Nm],F[2*Nm][2*Nm],De[Nm],Di[Nm],n;
int X[Nm*Nm],Y[Nm*Nm],m;
int Q[2*Nm],M[2*Nm],Pre[2*Nm];
void read()
{
int i;
freopen("harta.in","r",stdin);
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d%d",De+i,Di+i);
}
int BFS()
{
int l,r,x,i;
Q[l=r=0]=0;
Pre[0]=-2;
M[0]=Inf;
for(i=1;i<=2*n+1;i++)
Pre[i]=-1;
while(l<=r && Pre[2*n+1]==-1)
{
x=Q[l++];
for(i=1;i<=2*n+1;i++)
if(Pre[i]==-1 && F[x][i]<C[x][i])
{
Pre[i]=x;
M[i]=min(M[x],C[x][i]-F[x][i]);
Q[++r]=i;
}
}
return Pre[2*n+1]!=-1;
}
void solve()
{
int i,j;
for(i=1;i<=n;i++)
{
C[0][i]=De[i];
C[n+i][2*n+1]=Di[i];
for(j=n+1;j<=2*n;j++)
C[i][j]=1;
C[i][n+i]=0;
}
while(BFS())
{
i=2*n+1;
while(i)
{
F[Pre[i]][i]+=M[2*n+1];
F[i][Pre[i]]-=M[2*n+1];
i=Pre[i];
}
}
m=0;
for(i=1;i<=n;i++)
for(j=n+1;j<=2*n;j++)
if(F[i][j])
{
X[m]=i;
Y[m++]=j-n;
}
}
void write()
{
int i;
freopen("harta.out","w",stdout);
printf("%d\n",m);
for(i=0;i<m;i++)
printf("%d %d\n",X[i],Y[i]);
}
int main()
{
read();
solve();
write();
return 0;
}