0

嘿，我正在实施 ford-fulkerson 算法并找到最大流量。我只是从文本文件名中读取一些输入作为桥接并找到最大流量，但它显示索引 3 的错误超出长度 3 的范围。错误在第 24 行，它说的是我不明白为什么它显示错误. 任何人都请帮助解决这个问题。我已经尽力了，但我没有得到它的确切解决方案。

这是我的代码：

import java.io.File;
import java.io.FileNotFoundException;
import java.util.*;

public class MaxFlow {
    boolean[] found;
    int N;
    int[][] cap;
    int[][] flow;
    int[] dad;
    int[] dist;

    boolean searchFattest(int source, int sink) {
        Arrays.fill(found, false);
        Arrays.fill(dist, 0);
        dist[source] = Integer.MAX_VALUE / 2;
        while (source != N) {
            int best = N;
            found[source] = true;
            if (source == sink) break;
            for (int k = 0; k < N; k++) {
                if (found[k]) continue;
//                  System.out.println("cap: "+cap[source][k] + " flow: "+flow[source][k]);
                int possible = Math.min(cap[source][k] - flow[source][k], dist[source]);
                if (dist[k] < possible) {
                    dist[k] = possible;
                    dad[k] = source;
                }
                if (dist[k] > dist[best]) best = k;
            }
            source = best;
        }
        return found[sink];
    }

    boolean searchShortest(int source, int sink) {
        Arrays.fill(found, false);
        Arrays.fill(dist, Integer.MAX_VALUE/2);
        dist[source] = 0;
        while (source != N) {
            int best = N;
            found[source] = true;
            if (source == sink) break;
            for (int k = 0; k < N; k++) {
                if (found[k]) continue;
                if (cap[source][k] - flow[source][k] > 0) {
                    if (dist[k] > dist[source] + 1){
                        dist[k] = dist[source] + 1;
                        dad[k] = source;
                    }
                }
                if (dist[k] < dist[best]) best = k;
            }
            source = best;
        }
        return found[sink];
    }

    public int getMaxFlow(int[][] cap, int source, int sink) {
        this.cap = cap;
        N = cap.length;
        found = new boolean[N];
        flow = new int[N][N];
        dist = new int[N+1];
        dad = new int[N];

        int totflow = 0;
        while (searchFattest(source, sink)) {
            int amt = Integer.MAX_VALUE;
            for (int x = sink; x != source; x = dad[x])
                amt = Math.min(amt, cap[dad[x]][x] - flow[dad[x]][x]);
            for (int x = sink; x != source; x = dad[x]) {
                flow[dad[x]][x] += amt;
                flow[x][dad[x]] -= amt;
            }
            totflow += amt;
        }

        return totflow;
    }

    public static void main(String[] args) throws FileNotFoundException {
        MaxFlow flow = new MaxFlow();
        Scanner s = new Scanner(new File("C:\\Users\\Lenovo\\Documents\\bridge.txt"));
        int rows = 9;
        int columns = 3;
        int [][] myArray = new int[rows][columns];
        while(s.hasNextLine()) {
           for (int i=0; i<myArray.length; i++) {
              String[] line = s.nextLine().trim().split(" ");
              for (int j=0; j<line.length; j++) {
                 myArray[i][j] = Integer.parseInt(line[j]);
              }
           }
        }
        System.out.println(Arrays.deepToString(myArray));
//        int[][] cap = {{0},{1}};
        System.out.println(flow.getMaxFlow(myArray, 0, 5));
    }
}

这是它显示的错误：

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 3 out of bounds for length 3
at MaxFlow.searchFattest(MaxFlow.java:24)
at MaxFlow.getMaxFlow(MaxFlow.java:68)
at MaxFlow.main(MaxFlow.java:98)

这是我正在阅读的输入文件：bridge.txt

0 1 1
0 4 4
1 2 1
1 3 2
2 3 1
2 4 2
3 4 1
1 5 4
4 5 1
4

0 回答 0