Pagini recente » Cod sursa (job #679867) | Cod sursa (job #2283096) | Cod sursa (job #1841049) | Cod sursa (job #1313057) | Cod sursa (job #41736)
Cod sursa(job #41736)
#include <stdio.h>
#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();
void init();
void calc();
int bf();
int main()
{
read();
init();
calc();
return 0;
}
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()
{
int i,j;
while (bf() ==1 )
flux();
freopen("harta.out","w",stdout);
printf("%d\n",m);
for (i=1; i<=n; i++)
for (j=n+1; j<=2*n; j++)
if (fl[i][j] ==0)
printf("%d %d\n",i,j-n);
fclose(stdout);
}