Java P3376 #7 #8 RE

Shymeleaf @ 2022-11-27 21:17:41

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

/**
 * @author wangqiang6
 * @version 0.1
 * @description EK 算法
 * @date 2022-11-27
 */
public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] nmst = br.readLine().split(" ");
        int n = Integer.parseInt(nmst[0]);
        int m = Integer.parseInt(nmst[1]);
        int s = Integer.parseInt(nmst[2]);
        int t = Integer.parseInt(nmst[3]);
        resolve(n, m, s, t, br);
    }

    public static void resolve (int n, int m, int s, int t, BufferedReader br) throws IOException {
        // 1. 建图
        buildGraph(n, m, br);
        // 2. ek 算法开始
        preEdges = new int[n + 1]; // 因为题目：节点编号都是正数 1 ~ n；所以数组大小开到 n + 1
        minW = new long[n + 1]; // 同上
        long ans = 0;
        while (bfs(s, t)) {
            ans += minW[t];
            modifyEdgeWeight(s, t);
        }
        System.out.println(ans);
    }

    /**
     * 根据 pre 数组，从 target 出发，沿着新求出来的增广路径追溯回 source，
     * 修改增广路径每一条边的正向权重（剩余容量）和反向权重（剩余容量）
     * @param source
     * @param target
     */
    public static void modifyEdgeWeight(int source, int target) {
        int cur = target;
        while (cur != source) {
            int preEdge = preEdges[cur]; // pre 记录的是前驱边，取出来的是前驱边
            // 找到一条增广路径后，从 source 至 target 最小的 边的剩余容量 已求出，即 minW[target]
            // 随着 边剩余容量的 修改，从 source 可达 target 的所有路径上必定都会出现 某条边 剩余容量为 0，算法收敛
            edgeWeight[preEdge] -= minW[target];
            // 【细节4】在建图的时候，是添加一条边，就同时再添加其对应的反向边
            // 因此，下标 0 2 4 6 ... 2k 存的都是图中切实存在的边，而 1 3 5 7 ... 2k ^ 1 存的都是【同时添加的反向边】
            // 这里用 ^ 表示 +，因为偶数 + 1 肯定不会产生进位
            // 【重点】若 preEdge 本身为 图中存在的某条边的反向边，那么 ^ 1 后就会变成原来图中存在的某条边
            // 比如 3 是反向边（图中不存在），^ 1 之后【相当于做减法】，变成 2，是对于的图中存在的边，2 3 正好是一堆正反向边的关系
            edgeWeight[preEdge ^ 1] += minW[target];
            cur = edgeTo[preEdge ^ 1]; // 前一个节点就是 preEdge 对应边的反向边的目标节点 edgeTo[preEdge ^ 1]
        }
    }

    // pre[i] 节点 i 的前驱边
    public static int[] preEdges; // pre[i] 为 到节点 i 所经过的与 i 相连的边（同时可以标志 节点 i 是否被访问过
    // minW[i] 至点 i 为止，最小的【边的剩余容量】
    public static long[] minW;
    /**
     * source 到 target 寻找增广路径
     * @param source
     * @param target
     * @return
     */
    public static boolean bfs (int source, int target) {
        Arrays.fill(preEdges, -2); // -2 为节点 i 还未被访问过的标志
        Queue<Integer> queue = new LinkedList<>();
        preEdges[source] = -1; // 源节点的前驱边记为任意不存在的边，同时区别于 -2（未访问标志）即可
        queue.add(source);
        minW[source] = Integer.MAX_VALUE; // 重置【至 source 为止 最小的【边的剩余容量】】为 最大值
        while (!queue.isEmpty()) {
            int curNode = queue.poll();
            for (int e = head[curNode]; e != -1; e = nextEdge[e]) {
                int nextNode = edgeTo[e];
                if (preEdges[nextNode] == -2 && edgeWeight[e] > 0) { // 边关联的下一个节点没被访问过 && 边的剩余容量大于 0 才考虑
                    // 更新路径上的最小剩余容量
                    minW[nextNode] = Math.min(minW[curNode], edgeWeight[e]); // 【细节3】minW[i]的更新是直接算的（不用重置）
                    queue.add(nextNode);
                    preEdges[nextNode] = e;
                    if (nextNode == target) { // 找到了任意一条增广路径
                        return true;
                    }
                }
            }
        }
        return false;
    }

    /**
     * 邻接表存图
     */
    // 与每个节点关联的第一条边
    public static int[] head;
    // 每条边指向的节点
    public static int[] edgeTo;
    // 每条边的权重
    public static long[] edgeWeight;
    // 每条边在head[i] 链表中的下一条边
    public static int[] nextEdge;
    // 当前边的数量
    public static int nEdge;
    // 节点总数
    public static int nNode;
    // 处理重边的辅助数组 key from,to | value edgeNo
    public static Map<String, Integer> duplicateEdgeHelper;

    /**
     * 建图
     * @param n 节点数量
     * @param m 边数量
     * @param br
     */
    public static void buildGraph(int n, int m, BufferedReader br) throws IOException {
        head = new int[n + 1]; // 【细节2】节点编号为正整数，因此 节点编号从 1 ~ n
        Arrays.fill(head, -1); // head 初始化，所有节点都不与任何边关联
        edgeTo = new int[2 * m]; // 【细节5】每条边都有其对应的反向边，因此数组大小为 2 * m
        edgeWeight = new long[2 * m]; // 同上
        nextEdge = new int[2 * m]; // 同上
        nNode = n;
        duplicateEdgeHelper = new HashMap<>();
        for (int i = 0; i < m; i ++) {
            String[] inputs = br.readLine().split(" ");
            int from = Integer.parseInt(inputs[0]);
            int to = Integer.parseInt(inputs[1]);
            int weight = Integer.parseInt(inputs[2]);
            // 正向边
            addEdge(from, to, weight);
            // 反向边
            addEdge(to, from, 0);
        }
    }
    public static void addEdge(int from, int to, int weight) {
        if (duplicateEdgeHelper.containsKey(from + "," + to)) {
            // 【细节1】重复边权值累加，且 由于重边权值相加可能产生溢出，edgeWeight 需为 long[]
            edgeWeight[duplicateEdgeHelper.get(from + "," + to)] += weight;
            return ;
        }
        edgeTo[nEdge] = to;
        edgeWeight[nEdge] = weight;
        nextEdge[nEdge] = head[from];
        head[from] = nEdge;
        duplicateEdgeHelper.put(from + "," + to, nEdge ++);
    }
}

by Shymeleaf @ 2022-11-27 23:47:46

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

/**
 * @[author](/user/583141) wangqiang6
 * @version 0.1
 * @description EK 算法
 * @[date](/user/161966) 2022-11-27
 */
public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] nmst = br.readLine().split(" ");
        int n = Integer.parseInt(nmst[0]);
        int m = Integer.parseInt(nmst[1]);
        int s = Integer.parseInt(nmst[2]);
        int t = Integer.parseInt(nmst[3]);
        resolve(n, m, s, t, br);
    }

    public static void resolve (int n, int m, int s, int t, BufferedReader br) throws IOException {
        // 1. 建图
        buildGraph(n, m, br);
        // 2. ek 算法开始
        preEdges = new int[n + 1]; // 因为题目：节点编号都是正数 1 ~ n；所以数组大小开到 n + 1
        minW = new long[n + 1]; // 同上
        vis = new boolean[n + 1];
        long ans = 0;
        while (bfs(s, t)) {
            ans += minW[t];
            modifyEdgeWeight(s, t);
        }
        System.out.println(ans);
    }

    /**
     * 根据 pre 数组，从 target 出发，沿着新求出来的增广路径追溯回 source，
     * 修改增广路径每一条边的正向权重（剩余容量）和反向权重（剩余容量）
     * @[param](/user/590148) source
     * @[param](/user/590148) target
     */
    public static void modifyEdgeWeight(int source, int target) {
        int cur = target;
        while (cur != source) {
            int preEdge = preEdges[cur]; // pre 记录的是前驱边，取出来的是前驱边
            // 找到一条增广路径后，从 source 至 target 最小的 边的剩余容量 已求出，即 minW[target]
            // 随着 边剩余容量的 修改，从 source 可达 target 的所有路径上必定都会出现 某条边 剩余容量为 0，算法收敛
            edgeWeight[preEdge] -= minW[target];
            // 【细节4】在建图的时候，是添加一条边，就同时再添加其对应的反向边
            // 因此，下标 0 2 4 6 ... 2k 存的都是图中切实存在的边，而 1 3 5 7 ... 2k ^ 1 存的都是【同时添加的反向边】
            // 这里用 ^ 表示 +，因为偶数 + 1 肯定不会产生进位
            // 【重点】若 preEdge 本身为 图中存在的某条边的反向边，那么 ^ 1 后就会变成原来图中存在的某条边
            // 比如 3 是反向边（图中不存在），^ 1 之后【相当于做减法】，变成 2，是对于的图中存在的边，2 3 正好是一堆正反向边的关系
            edgeWeight[preEdge ^ 1] += minW[target];
            cur = edgeTo[preEdge ^ 1]; // 前一个节点就是 preEdge 对应边的反向边的目标节点 edgeTo[preEdge ^ 1]
        }
    }

    // pre[i] 节点 i 的前驱边
    public static int[] preEdges; // pre[i] 为 到节点 i 所经过的与 i 相连的边（同时可以标志 节点 i 是否被访问过
    // minW[i] 至点 i 为止，最小的【边的剩余容量】
    public static long[] minW;
    public static boolean[] vis;
    /**
     * source 到 target 寻找增广路径
     * @[param](/user/590148) source
     * @[param](/user/590148) target
     * @[return](/user/41710)
     */
    public static boolean bfs (int source, int target) {
        // Arrays.fill(preEdges, -2); // -2 为节点 i 还未被访问过的标志
        Arrays.fill(vis, false);
        Queue<Integer> queue = new LinkedList<>();
        // preEdges[source] = -1; // 源节点的前驱边记为任意不存在的边，同时区别于 -2（未访问标志）即可
        queue.add(source);
        vis[source] = true;
        minW[source] = Integer.MAX_VALUE; // 重置【至 source 为止 最小的【边的剩余容量】】为 最大值
        while (!queue.isEmpty()) {
            int curNode = queue.poll();
            for (int e = head[curNode]; e >= 0; e = nextEdge[e]) {
                int nextNode = edgeTo[e];
                if (!vis[nextNode] && edgeWeight[e] > 0) { // 边关联的下一个节点没被访问过 && 边的剩余容量大于 0 才考虑
                    // 更新路径上的最小剩余容量
                    minW[nextNode] = Math.min(minW[curNode], edgeWeight[e]); // 【细节3】minW[i]的更新是直接算的（不用重置）
                    queue.add(nextNode);
                    vis[nextNode] = true;
                    preEdges[nextNode] = e;
                    if (nextNode == target) { // 找到了任意一条增广路径
                        [return](/user/41710) true;
                    }
                }
            }
        }
        [return](/user/41710) false;
    }

    /**
     * 邻接表存图
     */
    // 与每个节点关联的第一条边
    public static int[] head;
    // 每条边指向的节点
    public static int[] edgeTo;
    // 每条边的权重
    public static long[] edgeWeight;
    // 每条边在head[i] 链表中的下一条边
    public static int[] nextEdge;
    // 当前边的数量
    public static int nEdge;
    // 节点总数
    public static int nNode;
    // 处理重边的辅助数组 key from,to | value edgeNo
    public static Map<String, Integer> duplicateEdgeHelper;

    /**
     * 建图
     * @[param](/user/590148) n 节点数量
     * @[param](/user/590148) m 边数量
     * @[param](/user/590148) br
     */
    public static void buildGraph(int n, int m, BufferedReader br) throws IOException {
        head = new int[n + 1]; // 【细节2】节点编号为正整数，因此 节点编号从 1 ~ n
        Arrays.fill(head, -1); // head 初始化，所有节点都不与任何边关联
        edgeTo = new int[2 * m]; // 【细节5】每条边都有其对应的反向边，因此数组大小为 2 * m
        edgeWeight = new long[2 * m]; // 同上
        nextEdge = new int[2 * m]; // 同上
        nNode = n;
        duplicateEdgeHelper = new HashMap<>();
        for (int i = 0; i < m; i ++) {
            String[] inputs = br.readLine().split(" ");
            int from = Integer.parseInt(inputs[0]);
            int to = Integer.parseInt(inputs[1]);
            int weight = Integer.parseInt(inputs[2]);
            // 正向边
            addEdge(from, to, weight);
            // 反向边
            addEdge(to, from, 0);
        }
    }
    public static void addEdge(int from, int to, int weight) {
        if (duplicateEdgeHelper.containsKey(from + "," + to)) {
            // 【细节1】重复边权值累加，且 由于重边权值相加可能产生溢出，edgeWeight 需为 long[]
            edgeWeight[duplicateEdgeHelper.get(from + "," + to)] += weight;
            [return](/user/41710) ;
        }
        edgeTo[nEdge] = to;
        edgeWeight[nEdge] = weight;
        nextEdge[nEdge] = head[from];
        head[from] = nEdge;
        duplicateEdgeHelper.put(from + "," + to, nEdge ++);
    }
}

改成这样之后 #7 #8 就 TLE 了

by Shymeleaf @ 2022-11-28 11:15:30

上述建图过程存在问题 添加一条边的时候，会同时添加其对应的反向边。 但是反向边不应该加到 map里面。