ISAP并行推流的算法写出来了，不过是java版的，放出来供参考：
```java
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.StreamTokenizer;
import java.util.ArrayDeque;
import java.util.Arrays;
public class Main implements Runnable {
static BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static StreamTokenizer st = new StreamTokenizer(buf);
public static int nextInt() throws IOException {
st.nextToken();
return (int) st.nval;
}
public static String nextString() throws IOException {
st.nextToken();
return st.sval;
}
public static void setNumStrMode() {
st.ordinaryChars('0', '9');
st.wordChars('0', '9');
st.ordinaryChar('.');
st.wordChars('.', '.');
}
//main
public static void main(String[] args) {
Main main = new Main();
new Thread(null, new Main(), "", 1 << 29).start();
}
@[Override](/user/542747)
public void run() {
mainFunc();
}
private void mainFunc() {
try {
int n = nextInt();
int m = nextInt();
int s = nextInt() - 1;
int t = nextInt() - 1;
init(n, m);
for (int i = 0; i < m; i++) {
int u = nextInt() - 1;
int v = nextInt() - 1;
int c = nextInt();
addEdge(v, u, 0, 0);
addEdge(u, v, c, 0);
}
System.out.println(maxflow(s, t));
} catch (IOException e) {
e.printStackTrace();
}
}
//code
static final long INF = 0x3f3f3f3f3f3f3f3fL;
//边 & 反向边
int[] to;
int[] nex;
int[] head;
int tot = 1; //反向边，初始化为1
int[] cap; //容量
int[] flow; //流量
int n, m, s, t;
boolean[] vis;
int[] d;
int[] cur;
int[] p;
int[] num;
long[] inFlow;
long[] outFlow;
public void addEdge(int u, int v, int cap, int flow) {
this.to[++tot] = v;
this.nex[tot] = head[u];
this.head[u] = tot;
this.cap[tot] = cap;
this.flow[tot] = flow;
}
public void init(int n, int m) {
this.n = n;
this.m = m;
//edge 从2开始
to = new int[m + 1 << 1];
nex = new int[to.length];
head = new int[n];
cap = new int[to.length];
flow = new int[to.length];
vis = new boolean[n];
d = new int[n];
p = new int[n];
num = new int[n + 1];
inFlow = new long[n];
outFlow = new long[n];
}
private boolean bfs() {
vis = new boolean[n];
ArrayDeque<Integer> queue = new ArrayDeque<>(n);
queue.addLast(t);
vis[t] = true;
d[t] = 0;
while (!queue.isEmpty()) {
int u = queue.removeFirst();
for (int t = head[u]; t > 0; t = nex[t]) {
int v = to[t];
//判断反边流量
if (!vis[v] && cap[t ^ 1] > flow[t ^ 1]) {
vis[v] = true;
d[v] = d[u] + 1;
queue.addLast(v);
}
}
}
return vis[s];
}
public long maxflow(int s, int t) {
this.s = s;
this.t = t;
long fl = 0L;
bfs();
for (int i = 0; i < n; i++) {
num[d[i]]++;
}
//dfs
int x = s;
cur = Arrays.copyOf(head, head.length);
inFlow[s] = INF;
outFlow[s] = 0;
while (d[s] < n) {
boolean flag = false;
if (x != t && inFlow[x] > outFlow[x]) {
for (int tt = cur[x]; tt > 0; tt = nex[tt]) {
int v = to[tt];
if (cap[tt] > flow[tt] && d[x] == d[v] + 1) {
flag = true;
inFlow[v] = Math.min(inFlow[x] - outFlow[x], cap[tt] - flow[tt]);
outFlow[v] = 0;
p[v] = tt;
cur[x] = tt;
x = v;
break;
}
}
}
if (!flag) {
//增广标记不成功
if (x == s) {
if (--num[d[x]] == 0) {
break;
}
int m = n - 1;
for (int i = head[x]; i > 0; i = nex[i]) {
int v = to[i];
if (cap[i] > flow[i]) {
m = Math.min(m, d[v]);
}
}
num[d[x] = m + 1]++;
cur[x] = head[x];
continue;
}
//目标t点，标记outFlow[x] = inFlow[x], 同时更新最大流fl
if (x == t) {
outFlow[x] = inFlow[x];
fl += outFlow[x];
}
//非s点，进行边的流标记，并更新入边pre节点的outFlow
if (x != s) {
int tt = p[x];
int pre = to[tt ^ 1];
outFlow[pre] += outFlow[x];
flow[tt] += outFlow[x];
flow[tt ^ 1] -= outFlow[x];
}
//当节点不是t，且有未推出的流时，表示此节点x在当前层与t节点不再联通，需要更新网络节点层
if (x != t && inFlow[x] > outFlow[x]) {
//当前层节点数减一，当前层为0则退出
if (--num[d[x]] == 0) {
break;
}
//计算x的可达节点的最小层m，默认为n-1
int m = n - 1;
for (int i = head[x]; i > 0; i = nex[i]) {
int v = to[i];
if (cap[i] > flow[i]) {
m = Math.min(m, d[v]);
}
}
//将x节点放入m+1层
num[d[x] = m + 1]++;
//重置x节点的当前弧优化
cur[x] = head[x];
}
//x!=s, x update to pre
if (x != s) {
x = to[p[x] ^ 1];
}
}
}
return fl;
}
//end code
}
```
by hulhul @ 2023-01-21 01:55:30