tatyam さんの解説 にあるように，この問題は最大 \(b\) マッチング問題と呼ばれる問題です．（同じ辺を複数回使えない場合には特に simple \(b\)-matching と呼ぶこともあります．）

入力: 無向グラフ \(G\)，頂点容量 \(b\colon V(G) \to \mathbb{Z}_{\ge 1}\).
目的: 辺部分集合 \(F \subseteq E(G)\) であって，各頂点 \(v \in V(G)\) に接続する \(F\) の辺の本数が \(b(v)\) 以下であるもののうち，サイズが最大のものを見つける．

特に \(b(v) = 1\) \((\forall v \in V)\) の場合は，最大マッチング問題と同じ問題です．さらに，任意の \(b\) の場合であっても，以下の変換により最大マッチング問題に帰着できます．

最大 \(b\) マッチング問題の入力 \((G, b)\) から，等価な最大マッチング問題の入力 \(G_b\) を構成します．

帰着イメージ図

各頂点 \(v \in V(G)\) に対して，\(b(v)\) 個の頂点 \(v_k\) \((k = 1, 2, \dots, b(v))\) を作成します．また，各辺 \(e = \{u, v\} \in E(G)\) に対して，\(2\) 個の頂点 \(e_u, e_v\) を作成します．これらを集めて \(G_b\) の頂点集合 \(V(G_b)\) とします．

各辺 \(e = \{u, v\} \in E(G)\) に対して，\(1 + b(u) + b(v)\) 本の辺を以下のように作成します．

• \(\{e_u, e_v\}\),
• \(\{u_k, e_u\}\) \((k = 1, 2, \dots, b(u))\),
• \(\{v_k, e_v\}\) \((k = 1, 2, \dots, b(v))\).

これらを集めて \(G_b\) の辺集合 \(E(G_b)\) とします．

このとき，\((G, b)\) における simple \(b\)-matching の最大サイズを \(\nu(G, b)\) と書き，\(G_b\) におけるマッチングの最大サイズを \(\nu(G_b)\) と書くことにすると，\(\nu(G, b) = \nu(G_b) - |E(G)|\) が成り立ちます．

証明

$(G, b)$ の最大 simple $b$-matching を $1$ つ選んで $F$ とします．このとき，各辺 $e = \{u, v\} \in F$ に対して辺 $\{u_k, e_u\}, \{v_\ell, e_v\}$ $(k \in \{1, 2, \dots, b(u)\}, \ell \in \{1, 2, \dots, b(v)\})$ を，互いに端点を共有しないように選べます．さらに，各辺 $e = \{u, v\} \in E(G) \setminus F$ に対して辺 $\{e_u, e_v\}$ を選びます．選ばれた辺の集合を $M$ とすると，これは $G_b$ のマッチングであって， $$|M| = 2|F| + |E(G) \setminus F| = |F| + |E(G)|$$ が成り立つので，$\nu(G_b) \ge \nu(G, b) + |E(G)|$ が示せました．

上で構成したマッチングが実際に最大であることを示します．もし最大でないとすると，増加道（非マッチ頂点から非マッチ頂点への単純パスであって，$M$ の辺と $E(G_b) \setminus M$ の辺を交互に通るようなもの）が存在します（よく分かるスライド）．増加道に沿ってマッチ辺と非マッチ辺を入れ替えて得られるマッチングを $M'$ とします．この操作でマッチ頂点は単調に $2$ 個増えるだけなので，$M$ の作り方から，各辺 $e = \{u, v\} \in E(G)$ に関する頂点 $e_u, e_v \in V(G_b)$ は何らかの辺でマッチされたままです．ここで，$F' \coloneqq \{\, e = \{u, v\} \in E(G) \mid f = \{e_u, e_v\} \in E(G_b) \setminus M' \,\}$ とすると，$F'$ は $G$ 中の simple $b$-matching であり，$|F'| > |F|$ を満たします．これは $F$ の最大性に矛盾するので，$M$ が $G_b$ 中の最大マッチングであることが導かれ，証明が完了しました．

変換後のグラフの頂点数は

\[|V(G_b)| = |E(G)| + \sum_{v \in V(G)} b(v) \le N^2 + \sum_i A_i\]

であり，辺数は

\[|E(G_b)| = |E(G)| + \sum_{v \in V(G)} \mathrm{deg}(v)b(v) \le N^2 + N\sum_i A_i\]

です（ \(\mathrm{deg}(v)\) は \(v\) に接続する辺数）．問題の制約から \(N \le \sum_i A_i\) なので，これらはいずれも \(2\left(\sum_i A_i\right)^2\) 以下です．

一般グラフの最大マッチング問題は，Micali–Vazirani アルゴリズム（ 2 部グラフの場合の Hopcroft–Karp アルゴリズムの一般化に相当するもの）を用いることで，\(n\) 頂点 \(m\) 辺のグラフに対して \(\mathrm{O}(\sqrt{n}m)\) 時間で解くことができます（概要がよくわかるスライド）．上の評価から，今回は \(\mathrm{O}\left(\left(\sum_i A_i\right)^3\right)\) 時間になるので，適切に実装することで制限時間に間に合わせることが可能です．

実装例 (C, 156 ms)