Pagini recente » Cod sursa (job #17212) | Cod sursa (job #1913492) | Cod sursa (job #3143577) | Cod sursa (job #648473) | Cod sursa (job #190305)
Cod sursa(job #190305)
#include <stdio.h>
#define input "harta.in"
#define output "harta.out"
#define nmax 300
#define maxim 300
int n,m,c[nmax][nmax],f[nmax][nmax],v[nmax],cap,coada,t[nmax],d[nmax][nmax];
int fm=0;
void citire()
{
int i,x,y;
freopen(input,"r",stdin);
scanf("%d",&n);
for (i=1;i<=n;i++)
{
scanf("%d %d",&x,&y);
c[0][i]=x;
c[n+i][n+n+1]=y;
}
}
int bfs()
{
int i,j,fol[nmax],nod;
cap=1,coada=1;
v[cap]=0;
for (i=1;i<=n+n+1;i++) fol[i]=0;
fol[0]=1;
while (cap<=coada)
{
nod=v[cap];
for (i=1;i<=n+n+1;i++)
if (c[nod][i]-f[nod][i]>0 && fol[i]==0)
{
coada++;
v[coada]=i;
t[i]=nod;
fol[i]=1;
}
cap++;
}
return fol[n+n+1];
}
int min(int a,int b)
{
if (a<b) return a;
return b;
}
void solve()
{
int i,j,flux,u;
for (i=1;i<=n;i++)
for (j=n+1;j<=n+n;j++)
if (i+n!=j) c[i][j]=1;
i=i;
while (bfs())
{
flux=maxim;
for (u=n+n+1;u;u=t[u])
flux=min(flux,c[t[u]][u]-f[t[u]][u]);
for (u=n+n+1;u;u=t[u])
{
f[t[u]][u]+=flux;
f[u][t[u]]-=flux;
}
fm++;
}
}
void afisare()
{
int i,j;
freopen(output,"w",stdout);
printf("%d\n",fm);
for (i=1;i<=n;i++)
for (j=n+1;j<=n+n;j++)
if (f[i][j]>0)
printf("%d %d\n",i,j-n);
}
int main()
{
citire();
solve();
afisare();
return 0;
}