Coursera Algorithm Ⅱ week3 baseball

全部代码https://github.com/Joshmomel/Princeton_Algorithms/tree/baseball

Context

通过maxflow来计算哪只队伍不能夺冠

1. g[i][j]代表i, j队伍还有多少场比赛
2. 这些比赛都连到team vertices, 图中有4队伍
3. t就是w[x] + r[x] - w[i], 代表i对最多能赢多少才不超过x队

对于图中w4+r4-w2代表49+27-69=7, Boston最多能赢6场比赛

代码

这次assignment的重点就是构建FlowNetwork

第一部分是构建g[i][j] 以及team vertices

    FlowNetwork flowNetwork = new FlowNetwork(this.vertices);
    List<String> computeTeams = teams.stream().filter(s -> !s.equals(team)).collect(Collectors.toList());

    int computeTeamLength = computeTeams.size();
    int counter = 0;
    for (int i = 0; i < computeTeamLength; i++) {
      for (int j = i + 1; j < computeTeamLength; j++) {
        counter += 1;
        flowNetwork.addEdge(new FlowEdge(0, counter, this.against(computeTeams.get(i), computeTeams.get(j))));
        flowNetwork.addEdge(new FlowEdge(counter, i + 1 + this.teamCombinations, Double.POSITIVE_INFINITY));
        flowNetwork.addEdge(new FlowEdge(counter, j + 1 + this.teamCombinations, Double.POSITIVE_INFINITY));
      }
    }

第二部分是把team vertices连接到t

    ArrayList<String> teamList = new ArrayList<>();
    int compareTeam = this.wins(teams.get(teams.indexOf(team))) + this.remaining(teams.get(teams.indexOf(team)));
    int i = 0;
    for (String computeTeam : computeTeams) {
      i += 1;
      if (compareTeam - this.wins(computeTeam) < 0) {
        teamList.add(computeTeam);
        return teamList;
      }
      flowNetwork.addEdge(new FlowEdge(i + this.teamCombinations, this.vertices - 1, compareTeam - this.wins(computeTeam)));
    }

第三部分是计算maxflow

    FordFulkerson maxflow = new FordFulkerson(flowNetwork, 0, this.vertices - 1);
    for (int v = 0; v < flowNetwork.V(); v++) {
      if (maxflow.inCut(v)) {
        int teamIndex = v - this.teamCombinations - 1;
        if (teamIndex >= 0) {
          String name = computeTeams.get(teamIndex);
          teamList.add(name);
        }
      }
    }

    return teamList.size() > 0 ? teamList : null;

其它部分包括numberOfTeams, teams, wins, losses, remaining, against 等可以参考这里

总结

这个作业重点是理解为什么maxflow可以解决这个问题, 并FlowNetwork做出来, 没有太多算法相关的内容