Pagini recente » Cod sursa (job #3250632) | Cod sursa (job #3176400) | Cod sursa (job #166928) | Cod sursa (job #1798571) | Cod sursa (job #282086)
Cod sursa(job #282086)
using namespace std;
#include<cstdio>
#include<iostream>
#define Nmax 101
int f[Nmax*2+2][Nmax*2+2],c[Nmax*2+2][Nmax*2+2],viz[Nmax*2+2],q[Nmax*2+2],s=0,d,m,n,t[Nmax*2+2];
int bfs()
{
q[0]=s;
viz[s]=1;
t[s]=0;
int p=0,x,i,u=0;
while(p<=u && !viz[d])
{
x=q[p];
p++;
for(i=0;i<=2*n+1;i++)
if(!viz[i] && f[x][i]<c[x][i])
{
viz[i]=1;
t[i]=x;
q[++u]=i;
}
}
if(viz[d]) return 0;
return 1;
}
void flux()
{
int i,l[Nmax*2+2],min,lg;
do
{
for(i=0;i<=2*n+2;i++) {viz[i]=0;t[i]=-1;}
if(bfs()) return;
l[0]=d; lg=0; min=c[ t[ l[0] ] ][d]-f[ t[ l[0] ] ][d];
while(l[lg]!=s)
{
++lg;
l[lg]=t[l[lg-1]];
if(c[l[lg]][l[lg-1]]-f[l[lg]][l[lg-1]]<min)
min=c[l[lg]][l[lg-1]]-f[l[lg]][l[lg-1]];
}
for(i=lg;i>0;i--)
{f[l[i]][l[i-1]]+=min;f[l[i-1]][l[i]]-=min;}
}while(1);
}
void read()
{
int i;
freopen("harta.in","r",stdin);
scanf("%d",&n); d=2*n+1;
for(i=1;i<=n;i++)
{
scanf("%d%d",&c[0][i],&c[n+i][2*n+1]);
}
}
int main()
{
int i,j;
read();
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i!=j) c[i][n+j]=1;
flux();
for(i=1;i<=n;i++) m+=c[0][i];
/*for(i=1;i<=n;i++)
{for(j=1;j<=n;j++)
cout<<f[i][n+j]<<" ";
cout<<endl;}*/
freopen("harta.out","w",stdout);
printf("%d\n",m);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(f[i][n+j]) printf("%d %d\n",i,j);
return 0;
}