Pagini recente » Cod sursa (job #2595047) | Cod sursa (job #2117439) | Cod sursa (job #610353) | Cod sursa (job #2555800) | Cod sursa (job #219795)
Cod sursa(job #219795)
#include<stdio.h>
#include<string.h>
#define N 205
int n,s,d,m;
int c[N][N],f[N][N],t[N],flux;
void citire()
{
int x,y,j;
for(int i=1; i<=n; i++)
{
scanf("%d%d",&x,&y);
c[0][i]=x;
c[i+n][d]=y;
m+=x;
for(j=1; j<=n; j++)
{
if(j==i)
continue;
c[i][j+n]=1;
}
}
}
bool bfs()
{
int p,u,nod,i,q[N];
memset(t,0xff,sizeof(t));
p=u=0;
q[0]=s;
t[s]=-1;
for(; p<=u; p++)
{
nod=q[p];
for(i=0; i<=d; i++)
{
if(t[i]==-1 && c[nod][i]>f[nod][i])
{
q[++u]=i;
t[i]=nod;
if(i==d)
return true;
}
}
}
return false;
}
int main()
{
freopen("harta.in","r",stdin);
freopen("harta.out","w",stdout);
scanf("%d",&n);
d=(n<<1)+1;
citire();
int i,j;
while(bfs())
{
/*i=d;
while(i!=s)
{
r=min(r,c[t[i]][i]-f[t[i]][i]);
i=t[i];
}*/
i=d;
while(i)
{
f[t[i]][i]++;
f[i][t[i]]--;
i=t[i];
}
}
printf("%d\n",m);
for(i=1; i<=n; i++)
{
for(j=n+1; j<d; j++)
{
if(f[i][j]>0)
printf("%d %d\n",i,j-n);
}
}
/*for(i=1; i<=n; i++)
{
for(j=n+1; j<d; j++)
printf("%d ",f[i][j]);
printf("\n");
}*/
//printf("%d\n",m);
//for(i=0; i<m; i++)
// printf("%d %d\n",v[i].x,v[i].y);
//printf("\n");
/*for(i=1; i<=n; i++)
printf("%d ",c[0][i]);
printf("\n");
for(i=1; i<=n; i++)
printf("%d ",c[i+n][d]);
printf("\n");*/
return 0;
}