Pagini recente » Cod sursa (job #177765) | Cod sursa (job #1530547) | Cod sursa (job #2393262) | Cod sursa (job #117151) | Cod sursa (job #184835)
Cod sursa(job #184835)
#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,-1,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]==-1)
{
T[i]=x;
l[++dr]=i;
if(i==2*n+1) return 1;
}
++st;
}
return 0;
}
#define min(a,b) (a)<(b)?(a):(b)
inline void flux()
{
int r;
while(bf())
{
for(i=1;i<=2*n;i++)
if(T[i] && a[i][2*n+1]-f[i][2*n+1]>=0)
{
x=i;
r=a[i][2*n+1]-f[i][2*n+1];
while(x!=0 && r)
{
r=min(r,a[T[x]][x]-f[T[x]][x]);
x=T[x];
}
if(!r) continue;
x=i;
f[i][2*n+1]+=r;
f[2*n+1][i]-=r;
while(x!=0)
{
f[T[x]][x]+=r;
f[x][T[x]]-=r;
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;
}