Pagini recente » Cod sursa (job #2748582) | Cod sursa (job #2973901) | Cod sursa (job #240903) | Cod sursa (job #318662) | Cod sursa (job #282522)
Cod sursa(job #282522)
using namespace std;
#include<cstdio>
#define Nmax 101
int n,s,d,viz[202],t[202],f[202][202],c[202][202];
int minim(int i,int j) {if(i<j) return i;return j;}
int bfs()
{
int Q[Nmax*2+2],p=0,u=0,i,x;
for(i=0;i<=2*n+2;i++) {viz[i]=0;t[i]=-1;}
viz[s]=1;
t[s]=0;
Q[0]=s;
while(p<=u)
{
x=Q[p];
p++;
for(i=1;i<=2*n+1;i++)
if(!viz[i] && f[x][i]<c[x][i])
{
viz[i]=1;
t[i]=x;
Q[++u]=i;
}
}
if(t[d]!=-1) return 1;
else return 0;
}
void flux()
{
int i,j,min;
while(bfs())
for(i=1;i<=n;i++)
{
min=c[n+i][d]-f[n+i][d];
for(j=n+i;j;j=t[j])
min=minim(min,c[t[j]][j]-f[t[j]][j]);
if(min>0)
{
for(j=n+i;j;j=t[j])
{
f[t[j]][j]+=min;
f[j][t[j]]-=min;
}
f[n+i][d]+=min;
f[d][n+i]-=min;
}
}
}
void read()
{
int i,j;
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][d]);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i!=j) c[i][n+j]=1;
}
int main()
{
int i,j,m=0;
read();
flux();
for(i=1;i<=n;i++) m+=c[0][i];
freopen("harta.out","w",stdout);
printf("%d\n",m);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
//printf("%d ",f[i][j+n]);
if(f[i][j+n]) printf("%d %d\n",i,j);
return 0;
}