}
return 0;
}
int bfs()
{
int i,j,base,top,x;
base=top=0;
for(i=0;i<=end;i++)
{
dis[i]=INF;
}
memset(status,0,sizeof(status));
queue[top++]=0;
dis[0]=0;
status[0]=1;
while(base
x=queue[base++];
status[x]=0;
for(i=1;i<=end;i++)
{
if(x!=i&&cap[x][i])
{
if(dis[i]>(dis[x]+cost[x][i]))
{
pre[i]=x;
dis[i]=(dis[x]+cost[x][i]);
if(!status[i])
{
status[i]=1;
queue[top++]=i;
}
}
}
}
}
{
return -1;
}else
{
return 1;
}
}
int EK()
{
int i,j,k,s=0;
int min=INF;
while(1)
{
k=bfs();
if(k==-1)
{
break;
}
for(i=end; i!=0; i=pre[i])
{
j=pre[i];
if(min>cap[j][i])
{
min=cap[j][i];
}
}
for(i=end; i!=0; i=pre[i])
{
j=pre[i];
s+=cost[j][i]*min;
cap[j][i]-=min;
cap[i][j]+=min;
}
}
return s;
}