Pagini recente » Cod sursa (job #2788731) | Cod sursa (job #2152291) | Cod sursa (job #353750) | Cod sursa (job #1352824) | Cod sursa (job #293768)
Cod sursa(job #293768)
#include<stdio.h>
#include<string.h>
FILE*fin=fopen("harta.in","r");
FILE*fout=fopen("harta.out","w");
#define nm 300
#define min(a,b)((a)<(b)?(a):(b))
#define infi 2000000000
int n,flow[nm][nm],cap[nm][nm],tata[nm],viz[nm],coada[nm];
struct nod
{
int inf;
nod *urm;
};
nod *g[nm];
int bfs()
{
int i,nd,nnd;
nod *q;
memset(viz,0,sizeof(viz));
coada[0]=1;
coada[1]=1;
viz[1]=1;
for(i=1;i<=coada[0];i++)
{
nd=coada[i];
q=g[nd];
while(q)
{
nnd=q->inf;
if(!viz[nnd]&&(cap[nd][nnd]-flow[nd][nnd]))
{
coada[0]++;
coada[coada[0]]=nnd;
viz[nnd]=1;
tata[nnd]=nd;
if(nnd==2*n+2) return 1;
}
q=q->urm;
}
}
return 0;
}
inline void add(int a,int b)
{
nod *q=new nod;
q->inf=b;
q->urm=g[a];
g[a]=q;
}
int main()
{
int i,j,flux=0,flux_crt,nd,a,b;
tata[1]=0;
memset(cap,0,sizeof(cap));
memset(flow,0,sizeof(flow));
fscanf(fin,"%d",&n);
for(i=1;i<=2*n+2;i++)
g[i]=NULL;
for(i=1;i<=n;i++)
{
fscanf(fin,"%d%d",&a,&b);
cap[1][i+1]=a;
cap[i+n+1][2*n+2]=b;
add(1,i+1);
add(i+1,1);
add(i+n+1,2*n+2);
add(2*n+2,i+n+1);
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i!=j)
{
cap[i+1][j+n+1]=1;
add(i+1,j+n+1);
add(j+n+1,i+1);
}
while(bfs())
{
flux_crt=infi;
nd=2*n+2;
while(tata[nd])
{
flux_crt=min(flux_crt,cap[tata[nd]][nd]-flow[tata[nd]][nd]);
nd=tata[nd];
}
flux+=flux_crt;
nd=2*n+2;
while(tata[nd])
{
flow[tata[nd]][nd]+=flux_crt;
flow[nd][tata[nd]]-=flux_crt;
nd=tata[nd];
}
}
fprintf(fout,"%d\n",flux);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i!=j) if(flow[i+1][j+n+1]==1) fprintf(fout,"%d %d\n",i,j);
fclose(fin);
fclose(fout);
return 0;
}