概略：大学・得意分野を頂点、人を辺としたグラフを考えると、元の問題は最大重みマッチングを求める問題になります。二部グラフの最大重みマッチングは最小費用流を用いて解けます。

次のようなグラフを構成します。

• ソースを表す頂点 \(S\)、シンクを表す頂点 \(T\)、大学を表す頂点 \(X_i\)、得意分野を表す頂点 \(Y_i\) を用意する
• 人 \(i\) を表す辺として、\(X_{A_i}\) から\(Y_{B_i}\) へ容量 \(1\) コスト \(C_i\) の辺を張る
• 各 \(i\) について、\(S\) から \(X_i\)、\(Y_i\) から \(T\) へ容量 \(1\)、コスト \(0\) の辺を張る

サンプル \(1\) に対するグラフは以下のようになります

このとき、\(i\) 人で構成されるドリームチームの強さの合計の最大値は、\(S\) から \(T\) への流量 \(i\) のフローの最大費用となります。十分大きな定数 \(\rm BIG\) を用いて辺のコストを次のように変更することで、最小費用流に変換できます

• 人 \(i\) を表す辺として、\(X_{A_i}\) から\(Y_{B_i}\) 間に容量 \(1\) コスト \({\rm BIG}-C_i\) の辺を張る

\(S\) から \(T\) への流量の最大値は \(M:=\min(\#\{A_i\},\#\{B_i\})\) なので、\(O(M(M+N)\log(M+N))\) でこの問題が解けました。