注：この解説では数学の記号・用語をいい加減に用いています。

この解説は本質的に公式解説と等価です。「分割マトロイド」などの言葉を明示的に使っていないだけです。

解法の思い浮かべ方

この問題は全ての \(i\) で \(A_i=1\) なら最大マッチング問題です。よって最大マッチング問題を一般化した問題であるとみなす事ができます。最大マッチング問題の一般化といえば線形マトロイドパリティです（？）

線形マトロイドパリティ

線形マトロイドパリティとは次の問題です。

ベクトルの組 \((a_1, b_1), (a_2, b_2), \dots, (a_N, b_N)\) が与えられたとき、 \(I\subset \{1,2,\dots,N\}\) であって、\(\{a_i \mid i\in I\}\cup \{b_i \mid i\in I\}\) の \(2|I|\) 個のベクトルが線形独立になるような \(|I|\) の最大値を求めよ

最大マッチングの線形マトロイドパリティへの帰着

\(G\) を頂点数 \(N\) 、辺数 \(M\) のグラフとし、辺を \((u_i,v_i)\) とします。\(N\) 次元ベクトル空間の元で、\(i\) 番目の成分のみが \(1\) で他が \(0\) であるベクトルを \(e_i\) とします。\(a_i=e_{u_i}, b_i=e_{v_i}\) と定めた \(M\) 個のベクトルの組 \((a_i,b_i)\) から定まる線形マトロイドパリティは最大マッチング問題と同値です。

元の問題の線形マトロイドパリティへの帰着

頂点 \(i\) を含む辺たちについて、\(A_i\) 次元のランダムなベクトルを割り当てることにします。するとそれらの辺たちからは高々 \(A_i\) 本までしか線形独立なベクトルを取ることができません。よってこの条件を全ての \(i\) について同時に課すよう、各頂点ごとの \(A_i\) 次元のベクトル空間の直和をとった \(\sum_i A_i\) 次元のベクトル空間を考えることで、線形マトロイドパリティに帰着することができます。