Pagini recente » Cod sursa (job #1076372) | Cod sursa (job #594545) | Cod sursa (job #973725) | Cod sursa (job #177019) | Cod sursa (job #423825)
Cod sursa(job #423825)
#include<stdio.h>
#include<string.h>
#define Nmax 210
int n,cap[Nmax][Nmax],fl[Nmax][Nmax],S,D,viz[Nmax],c[Nmax],t[Nmax],nrt;
struct nod
{
int inf;
nod *urm;
}*a[Nmax];
void citire()
{
int i,x,y;
nod *p;
for(i=1;i<=n;i++)
{
scanf("%d %d",&x,&y);
p=new nod;
p->inf=i;
cap[S][i]=x;
p->urm=a[S];
a[S]=p;
p=new nod;
p->inf=S;
p->urm=a[i];
a[i]=p;
p=new nod;
p->inf=D;
cap[i+n][D]=y;
p->urm=a[i+n];
a[i+n]=p;
p=new nod;
p->inf=i+n;
p->urm=a[D];
a[D]=p;
nrt+=x;
}
}
int BFS()
{
memset(viz,0,sizeof(viz));
c[1]=S;
viz[S]=1;
int p,u;
p=u=1;
nod *pp;
while(p<=u)
{
if(c[p]!=D)
for(pp=a[c[p]];pp!=NULL;pp=pp->urm)
if(viz[pp->inf]==0 && cap[c[p]][pp->inf]>fl[c[p]][pp->inf])
{
u++;
c[u]=pp->inf;
viz[pp->inf]=1;
t[pp->inf]=c[p];
}
p++;
}
return viz[D];
}
int main()
{
freopen ("harta.in","r",stdin);
freopen ("harta.out","w",stdout);
scanf("%d",&n);
S=0;
D=2*n+1;
nod *p;
int i,j,minim;
citire();
for(i=1;i<=n;i++)
for(j=n+1;j<=2*n;j++)
if(i!=j-n)
{
p=new nod;
p->inf=j;
p->urm=a[i];
a[i]=p;
p=new nod;
p->inf=i;
p->urm=a[j];
a[j]=p;
cap[i][j]=1;
}
printf("%d\n",nrt);
while(BFS())
{
for(p=a[D];p!=NULL;p=p->urm)
{
if(cap[p->inf][D]-fl[p->inf][D]>0 && viz[p->inf])
{
minim=cap[p->inf][D]-fl[p->inf][D];
int aj;
aj=p->inf;
while(aj!=S)
{
if(minim>cap[t[aj]][aj]-fl[t[aj]][aj])
minim=cap[t[aj]][aj]-fl[t[aj]][aj];
aj=t[aj];
}
if(minim==0) continue;
fl[p->inf][D]+=minim;
fl[D][p->inf]-=minim;
aj=p->inf;
while(aj!=S)
{
fl[t[aj]][aj]+=minim;
fl[aj][t[aj]]-=minim;
aj=t[aj];
}
}
}
}
//printf("\n\n");
for(i=1;i<=n;i++)
for(j=n+1;j<=2*n;j++)
if(fl[i][j]==1)
printf("%d %d\n",i,j-n);
return 0;
}