bool makelevel() { memset(level,-1,sizeof(level)); q[1]=0; level[0]=0; head=1,tail=1; for(int head=1;head<=tail;head++) { for(int i=lin[q[head]];i;i=e[i].next) { if(level[e[i].y]<0&&e[i].v>0) { level[e[i].y]=level[q[head]]+1; q[++tail]=e[i].y; } } } return level[n+m+1]>=0; } int MAXflow(int aa,int flow) { if(aa==n+m+1)return flow; int maxflow=0,d=0; for(int i=lin[aa];i&&maxflow<flow;i=e[i].next) { if(e[i].v&&level[e[i].y]==level[aa]+1) { if(d=MAXflow(e[i].y,min(flow-maxflow,e[i].v))) { e[i].v-=d; e[e[i].h].v+=d; maxflow+=d; } } } if(maxflow<=0) level[aa]=-1; return maxflow; } void dinic() { int d; while(makelevel()) while(d=MAXflow(0,99999999)) ans+=d; }