Pagini recente » Cod sursa (job #160423) | Cod sursa (job #1142383) | Cod sursa (job #500538) | Cod sursa (job #1970946) | Cod sursa (job #219535)
Cod sursa(job #219535)
#include<stdio.h>
#include<string.h>
#define INF 1<<30
#define N 205
int n,s,d,m;
struct ajt
{
int x,y;
};
ajt v[5052];
int c[N][N],f[N][N],t[N],flux;
inline int min(int x,int y)
{
return x<y ? x : y;
}
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;
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,0,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] && 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 r,i,j;
for(flux=0; bfs(); flux+=r)
{
r=INF;
i=d;
while(i!=s)
{
r=min(r,c[t[i]][i]-f[t[i]][i]);
i=t[i];
}
i=d;
while(i!=s)
{
f[t[i]][i]+=r;
f[i][t[i]]-=r;
i=t[i];
}
}
for(i=1; i<=n; i++)
{
for(j=n+1; j<d; j++)
{
if(f[i][j]>0)
{
v[m].x=i;
v[m].y=j-n;
m++;
}
}
}
/*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;
}