ProjectSelection(Pathfinder)_Vlad

class ProjectSelection {

    public static
    /**
     * You should implement this method
     *
     * @param projects List of projects, you can ignore list.get(0)
     * @return A set of feasible projects that yield the maximum possible profit.
     */
    int maximumProjects(List<Project> projects) {
        // TODO
        int n = projects.size();
        List<Node> nodes = new ArrayList<>();
        Node[] nodesArr = new Node[n + 1];

        for (int i = 1; i <= n; ++i)
        {
          nodesArr[i] = new Node(i);
          nodes.add(nodesArr[i]);
        }

        Node source = new Node(-1);
        Node sink = new Node(-2);

        nodes.add(source);
        nodes.add(sink);

        Integer allPossibleProfits = 0;

        for (Project project: projects) {
          int profit = project.getRevenue() - project.getCost();
          if (profit > 0) {// link to source as it generates profit
            source.addEdge(nodesArr[project.getId()], profit);
            allPossibleProfits += profit;
          }
          else { // link to sink as it costs (profit < 0; cost = -profit)
            nodesArr[project.getId()].addEdge(sink, - profit);
          }
        }

        for (Project task: projects)
          for (Integer subtaskId: task.getRequirements())
            nodesArr[task.getId()].addEdge(nodesArr[subtaskId], Integer.MAX_VALUE / 2);


        Graph G = new Graph(nodes, source, sink);
        int allCosts = MaxFlow.maximizeFlow(G);
        return allPossibleProfits - allCosts;
    }
}