Pagini recente » Cod sursa (job #1504195) | Cod sursa (job #776956) | Cod sursa (job #402592) | Cod sursa (job #2625549) | Cod sursa (job #180631)
Cod sursa(job #180631)
#include <cstdio>
#define nmax 101
int fl[2*nmax+1][2*nmax+1], tata[2*nmax+1], lista[2*nmax+1], min[nmax],mout[nmax],n,m,sursa,dest;
void read()
{
int i;
freopen("harta.in","r",stdin);
scanf("%d", &n);
for (i=1; i<=n; i++)
{
scanf("%d%d", &mout[i], &min[i]);
m+=mout[i];
}
fclose(stdin);
sursa=0;
dest=2*n+1;
}
void init()
{
int i,j;
for (i=1; i<=n; i++)
fl[sursa][i]=mout[i];
for (i=n+1; i<=2*n; i++)
fl[i][dest]=min[i-n];
for (i=1; i<=n; i++)
for (j=n+1; j<=2*n; j++)
if (i!=j-n)
fl[i][j]=1;
else
fl[i][j]=-1;
}
int bf()
{
int i,j,k=1;
for (i=sursa; i<=dest; i++)
tata[i]=-1;
lista[1]=0; i=1;
tata[0]=0;
while (i<=k)
{
for (j=sursa; j<=dest; j++)
if (fl[lista[i]][j]>0 && tata[j] ==-1)
{
tata[j]=lista[i];
k+=1;
lista[k]=j;
if (j==dest)
{
i=k;
break;
}
}
i+=1;
}
if (tata[dest]!=-1)
return 1;
else
return 0;
}
void flux()
{
int i=dest,j;
while (i !=0)
{
j=tata[i];
fl[j][i]-=1;
fl[i][j]+=1;
i=j;
}
}
void calc()
{
while (bf() ==1 )
flux();
freopen("harta.out","w",stdout);
printf("%d\n",m);
for (int i=1; i<=n; i++)
for (int j=n+1; j<=2*n; j++)
if (fl[i][j]==0)
printf("%d %d\n",i,j-n);
fclose(stdout);
}
int main()
{
read();
init();
calc();
return 0;
}