int head[N],cur[N],pre[N],d[N],gap[N]; int n,m,hcnt,S,T; struct Node{ int to,nxt,v; Node(){} Node(int a,int b,int c):to(a),nxt(b),v(c){} }node[maxn]; inline void add(int x,int y,int v){ node[hcnt]=Node(y,head[x],v);head[x]=hcnt++; node[hcnt]=Node(x,head[y],0);head[y]=hcnt++; } bool ISAP(int S,int T,int n){ ///起点,终点,总共点数(加上源汇点) int ans=0,aug=inf,i,flag; ///最大流,可增广流量,.,标记 int u,e,dis; ///当前点,当前可达点 mst(gap,0);mst(d,0); for(i=0;i<=n;++i) cur[i]=head[i]; u=pre[S]=S; while(d[S]<n){ flag=0; for(i=cur[u];~i;i=node[i].nxt){ e=node[i].to; if(node[i].v>0&&d[u]==d[e]+1){ flag=1; break; } } if(flag){ pre[e]=u; cur[u]=i; aug=min(aug,node[i].v); u=e; if(u==T){ while(u!=S){ u=pre[u]; node[cur[u]].v-=aug; node[cur[u]^1].v+=aug; } u=S; ans+=aug; aug=inf; } } else{ if(--gap[d[u]]==0)break; dis=n; cur[u]=head[u]; for(int i=head[u];~i;i=node[i].nxt){ e=node[i].to; if(node[i].v>0&&d[e]+1<dis){ dis=d[e]+1; cur[u]=i; } } d[u]=dis; ++gap[dis]; if(u!=S) u=pre[u]; } } return ans; }