ISAP模板（网络流模板）

 附上学习地址：

https://www.luogu.org/blog/ONE-PIECE/jiu-ji-di-zui-tai-liu-suan-fa-isap-yu-hlpp

ISAP过不掉的题：

https://loj.ac/problem/127

const int maxn = 1e4 + 3000;
const int maxm = 4e5 + 10;
const int inf = 1 <<30;
int s, t;
int n, m;
int maxflow;
int cnt, head[maxn], curedge[maxn];
int depth[maxn], gap[maxn];
//depth[i]表示节点i的深度，gap[i]表示深度为i的点的数量
struct Node {int v;int c;int nex;
} edge[maxm];
void init(){cnt = 0;memset(head, -1, sizeof(head));
}
inline void addedge(int u, int v, int c) {//正向建边edge[cnt] = { v, c, head[u] };head[u] = cnt++;//反向建边edge[cnt] = { u, 0, head[v] };head[v] = cnt++;
}
void bfs() { //从t到s进行分层 memset(depth, -1, sizeof(depth));memset(gap, 0, sizeof(gap));depth[t] = 0;gap[0] = 1;queue que;que.push(t);while (!que.empty()) {int u = que.front();que.pop();//遍历u 的所有出边 for (int i = head[u]; i != -1; i = edge[i].nex) {int v = edge[i].v;if (depth[v] != -1) //已经被分过层 continue;que.push(v);depth[v] = depth[u] + 1; // v是u 的下一层 gap[depth[v]]++; //深度为depth[v]的点的数量+1 }}return;
}
int dfs(int u, int flow) {if (u == t) { // 可以到达t maxflow += flow;return flow;}int used = 0; //用来表示这个点的流量用了多少for (int &i = curedge[u]; i != -1; i = edge[i].nex) {int v = edge[i].v;if (edge[i].c && depth[v] + 1 == depth[u]) {int mi = dfs(v, min(edge[i].c, flow - used)); // 找出增广路上最少的流量 if (mi) { // 找到增广路 edge[i].c -= mi; //正向边- edge[i ^ 1].c += mi; //反向边+ used += mi; //当前点流量+ }if (used == flow) //u的能流出的流量流完 return used;}}//前半段和Dinic一模一样//如果已经到了这里，说明该点出去的所有点都已经流过了//并且从前面点传过来的流量还有剩余//则此时，要对该点更改dep//使得该点与该点出去的点分隔开curedge[u] = head[u]; //当前狐优化退回到最初 --gap[depth[u]]; //深度为depth[u] /*这里要解释一下为什么要统计每个深度的点数：为了优化！？统计每个深度对应点数只为了这句话：if (gap[depth[u]] == 0) //出现断层，无法到达t了 depth[s] = n + 1;因为我们是按照深度来往前走的，路径上的点的深度一定是连续的，而t的深度为0，如果某个深度的点不存在，那么我们就无法到达t了*/if (gap[depth[u]] == 0) //出现断层，无法到达t了 depth[s] = n + 1;depth[u]++; // 层数++ gap[depth[u]]++; //层数对应个数++ return used;
}
int ISAP() {maxflow = 0;bfs();for (int i = 0; i <= n; ++i) curedge[i] = head[i];while (depth[s] }