ISAP能并行推流么？

hulhul @ 2023-01-20 19:00:02

by hulhul @ 2023-01-21 01:55:30

ISAP并行推流的算法写出来了，不过是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
}