G - Dream Team Editorial by en_translator

TL; DR: considering a graph where universities and subjects are vertices and people are edges, the original problem boils down to a maximum weight matching problem. A maximum matching problem on a bipartite graph can be solved with minimum cost flow problem.

Construct the following graph.

  • Prepare a vertex \(S\) that represents the source, \(T\) for the sink, \(X_i\) for each university, and \(Y_i\) for each subject.
  • Add an edge from \(X_{A_i}\) to \(Y_{B_i}\) with capacity \(1\) and cost \(C_i\) that represents the \(i\)-th programmer.
  • Add edges from \(S\) to \(X_i\) and \(X_i\) to \(T\) with capacities \(1\) and costs \(0\) for each \(i\).

The graph corresponding to Sample \(1\) looks like as follows.


Here, the maximum sum of power of a dream team consisting of \(i\) people is the maximum cost of a flow of amount \(i\) from \(S\) to \(T\). By modifying the costs of edges using a sufficiently large constant \(\rm BIG\), the problem can be transformed into a minimum cost flow problem.

  • Add an edge from \(X_{A_i}\) to \(Y_{B_i}\) with capacity \(1\) and cost \({\rm BIG}-C_i\) that represents the \(i\)-th programmer.

The maximum flow from \(S\) to \(T\) is \(M:=\min(\#\{A_i\},\#\{B_i\})\), so the problem has been solved in a total of \(O(M(M+N)\log(M+N))\) time.

last update: