boolbfs()// 广搜 { for (int i=0;i<N;++i) vis[i]=0; d[S]=1e8; while (q.size()) q.pop(); vis[S]=1; q.push(S); while (q.size()) { int x=q.front();q.pop(); for (int i=h[x];i!=-1;i=ne[i]) { if (vis[e[i]]) continue; if (w[i]!=0) { vis[e[i]]=1; d[e[i]]=min(d[x],w[i]); pre[e[i]]=i;//记录前驱 if (e[i]==T) returntrue; q.push(e[i]); } } } returnfalse; }
intEdmonds_Karp() { int r=0; while (bfs()) { int f=d[T]; for (int i=T;i!=S;i=e[pre[i]^1]) { w[pre[i]]-=f; w[pre[i]^1]+=f;//反向边加上对应流量 } r+=f; } return r; }
boolbfs() { memset(d,-1,sizeof d); while (q.size()) q.pop(); q.push(S); d[S]=0;cur[S]=h[S];//cur 是指当前到的出边 while (q.size()) { int t=q.front();q.pop(); for (int i=h[t];i!=-1;i=ne[i]) { if (d[e[i]]==-1&&w[i]) { d[e[i]]=d[t]+1; cur[e[i]]=h[e[i]]; if (e[i]==T) returntrue; q.push(e[i]); } } } returnfalse; }
intfind(int u,int lim) { if (u==T) return lim; int flow=0; for (int i=cur[u];i!=-1&&flow<lim;i=ne[i]) {//没有剩余流量就直接退出 cur[u]=i;// 当前弧优化,下一次从这一条边出发 if (d[e[i]]==d[u]+1&&w[i]) { int t=find(e[i],min(w[i],lim-flow)); if (t!=0) d[e[i]]=-1; // 没有路径,就不再访问,赋值为-1 w[i]-=t,w[i^1]+=t,flow+=t; } } return flow; } intdinic() { int r=0,flow=0; while (bfs()) while (flow=find(S,INF)) r+=flow; return r; }