ProjectSelectionWL10_Vlad

package weblab;

import java.util.*;

class Solution {

    /**
     * @param n The number of members of the Camel Club
     * @param m The number of jobs for the club
     * @param mNames The names of the members, in indices 1 to n.
     * @param t The times that each member is available, in indices 1 to n.
     * @param ms The skillsets of each member, in indices in 1 to n.
     * @param jobNames The names/descriptions of the jobs, in indices 1 to m.
     * @param p The times that each job takes, in indices 1 to m.
     * @param js The skillsets required for each job, in indices 1 to m.
     * @return true iff the club can complete all jobs.
     */
    public static boolean solve(
            int n,
            int m,
            String[] mNames,
            int[] t,
            Set<String>[] ms,
            String[] jobNames,
            int[] p,
            Set<String>[] js) {
      List<Node> nodes = new ArrayList<>();

      Node[] members = new Node[n + 1];
      Node[] jobs = new Node[m + 1];
      Node source = new Node("src");
      Node sink = new Node("dst");
      nodes.add(source);
      nodes.add(sink);

      for (int i = 1; i <= n; ++i) {
        members[i] = new Node(mNames[i]);
        nodes.add(members[i]);
        source.addEdge(members[i], t[i]);
      }

      for (int j = 1; j <= m; ++j) {
        jobs[j] = new Node(jobNames[j]);
        nodes.add(jobs[j]);
        jobs[j].addEdge(sink, p[j]);
      }


      for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
          if (ms[i].containsAll(js[j]))  // If member 'i' can fulfill all the requirements of job 'j'
            members[i].addEdge(jobs[j], Integer.MAX_VALUE / 2);


      Graph G = new Graph(nodes, source, sink);
      G.maximizeFlow();

      int jobTimes = 0;
      for (int j = 1; j <= m; ++j)
        jobTimes += p[j];

      for (Edge e: sink.getEdges()) {
        Edge term = e.getBackwards();
        jobTimes -= term.getFlow();
      }

      return jobTimes == 0; // If all jobs were fulfilled -> all edges (node, t) are saturated by flow

    }
}