作业地址：http://http://coursera.cs.princeton.edu/algs4/assignments/baseball.html
作业难点：
1、如何计算非平凡淘汰（Nontrivial elimination）？
关键在于理解题目的这句话“If all edges in the maxflow that are pointing from s are full, then this corresponds to assigning winners to all of the remaining games in such a way that no team wins more games than x. If some edges pointing from s are not full, then there is no scenario in which team x can win the division.”
1）平凡淘汰：从所有队伍中直接淘汰w[i] + r[i] < max{w[i]}的队伍；
2）在剩余的队伍中，分别以w[i] + r[i]作为所有队伍必须完成的胜场次数，估算[team vertices] -> [sink vertice]的capacity：w[i] + r[i] - w[j]，然后按题目提示：
| from | to | capacity |
| [source vertice] | [game vertices] | game[i][j] |
| [game vertices] | [team vertices] | infinity |
| [team vertices] | [sink vertice] | w[i] + r[i] - w[j] |
构建FlowNetWork；
3）通过FordFulkerson算法求解每个w[i] + r[i]下的流量，确定是否达到最大流量，如果没有达到最大流量，说明比赛没有进行完所有队伍的胜场已达到w[i]+r[i]，亦即最终获胜的队伍胜场大于w[i]+r[i]，说明这第i支队伍需要被淘汰；
2、如何计算队伍是被哪些队伍淘汰的？
1）平凡淘汰：队伍是被目前领先的队伍直接淘汰；
2）非平凡淘汰：根据最大流最小切定理（以及题目提示：What the min cut tells us.），队伍被过source的最小切上的顶点所淘汰。
容易扣分点：
本题目的特征是要么没有理解题意难以求解，要么很顺利得出最终结果。
部分代码：
1、数据结构：
private int[] w, l, r; private int[][] games; private Map<String, Integer> teamMap; private int maxWins = -1; private String leadingTeam; private static final double MAX_EDGE = Double.POSITIVE_INFINITY; private class spGraph { FordFulkerson ff; FlowNetwork flowNetwork; int s; public spGraph(FordFulkerson ff, FlowNetwork network, int source, int sink) { super(); this.ff = ff; this.flowNetwork = network; this.s = source; } }
2、构造网络流图：
private spGraph buildGraph(int id) { int n = numberOfTeams(); int source = n; int sink = n + 1; int gameVertice = n + 2; int curMaxWins = w[id] + r[id]; Set<FlowEdge> edges = new HashSet<FlowEdge>(); for (int i = 0; i < n; i++) { if (i == id || trvialEnd(i)) continue; for (int j = 0; j < i; j++) { if (j == id || trvialEnd(j) || games[i][j] == 0) continue; edges.add(new FlowEdge(source, gameVertice, games[i][j])); edges.add(new FlowEdge(gameVertice, i, MAX_EDGE)); edges.add(new FlowEdge(gameVertice, j, MAX_EDGE)); gameVertice++; } edges.add(new FlowEdge(i, sink, curMaxWins - w[i])); } FlowNetwork flowNetwork = new FlowNetwork(gameVertice); for (FlowEdge edge : edges) flowNetwork.addEdge(edge); FordFulkerson ff = new FordFulkerson(flowNetwork, source, sink); return new spGraph(ff, flowNetwork, source, sink); }
普林斯顿算法课Part2第三周作业_BaseballElimination
原文：http://www.cnblogs.com/notTao/p/6367733.html
