原案:admin

この問題は \(2\) 通りの考察方法があります。最終的に似たようなグラフ構成にたどり着きますが、それぞれ紹介します。

①二部グラフをad-hocに構成

\(2N\) 個の頂点 \(A_1,A_2,\dots,A_N,B_1,B_2,\dots,B_N\) を用意します。
\(m=1,2,\dots,M\) について、\(A_{u_m}\) と \(B_{v_m}\)、\(A_{v_m}\) と \(B_{u_m}\) をそれぞれ辺で結びます。
このグラフにおける最大独立集合 \(MIS\) を一つ取ります。 答えが \(1013 \times |MIS|\) であることを示します。

\(f(v)=\begin{cases}1(v \in MIS)\\0 (v\notin MIS)\end{cases}\)
とします。 \(i=1,2,\dots,N\) について、\(W_i=1013 \times (f(A_i)+f(B_i))\) と重みを割り当てることにします。
\(m=1,2,\dots,M\) について、\(f(A_{u_m})+f(B_{v_m}), \; f(A_{v_m})+f(B_{u_m})\) はいずれも \(1\) 以下なので、\((W_{u_m}+W_{v_m}) \leq 1013 \times (1+1)=2026\) が成り立ちます。 よって、答えは \(1013 \times |MIS|\) 以上であることがわかります。

構成したグラフの孤立点を \(IP_1,IP_2,\dots,IP_K\) として、孤立点を取り除いたグラフにおいて最小辺被覆 \(MEC\) を一つ取ります。
構成したグラフは二部グラフであることから、\(|MIS|=|MEC|+K\) です。
最小辺被覆の定義から、 \(2 \times \sum_{i=1}^{N}{W_i} \leq \sum_{k=1}^{K}{W_{IP_k}}+ \sum_{(u,v) \in MEC}{W_u+W_v} \leq 2026 \times K+2026 \times |MEC|=2026 \times |MIS|\)
なので
\(\sum_{i=1}^{N}{W_i} \leq 1013 \times |MIS|\) です。

以上により、求める答えは \(1013 \times |MIS|\) であることが示せました。

②最大独立集合のLP緩和解の半整数性+最小カット

重みに割り当てる値を整数から実数に拡張します。
\(P_-=\{v|0 \lt W_v \lt 1013\}\)
\(P_+=\{v|2026 \gt W_v \gt 1013\}\)
として、\(\sum_{i=1}^{N}{W_i}\) が最大となるもののうち \(|P_- \cup P_+|\) が最小となるようなものを取ります。

\(P_- \cup P_+ \neq \emptyset\)
と仮定します。 \(d=\min(1013-\max(P_-),\min(P_+)-1013)\) と置きます。
\(|P_+| \lt |P_-|\) ならば、\(P_+\) に含まれる各 \(v\) に対して \(W_v\) から \(d\) を引き、\(P_-\) に含まれる各 \(v\) に対して \(W_v\) に \(d\) を足すとさらに \(\sum_{i=1}^{N}{W_i}\) を大きくできるので、\(|P_+| \geq |P_-|\) です。
同様に \(|P_+| \leq |P_-|\) であることもわかるので、\(|P_+| = |P_-|\) です。
\(P_+\) に含まれる各 \(v\) に対して \(W_v\) から \(d\) を引き、\(P_-\) に含まれる各 \(v\) に対して \(W_v\) に \(d\) を足すと、\(|P_- \cup P_+|\) をさらに小さくすることができて矛盾します。
したがって、\(P_- \cup P_+ = \emptyset\) であり、\(W_v \in \{0,1013,2026\}\) としてよいことがわかります。
\(W_v\) を \(1013\) で割って、各頂点に \(0,1,2\) の重みを割り当てる問題に言い換えます。

• \(v\) に \(W_v\) を割り当てるとコストが \(-W_v\) かかる
• \(W_{u_m}+W_{v_m} \geq 3\) ならばコストが \(\infty\) かかる

というルールの元でコストを最小化する問題が解ければよいです。

各頂点 \(v\) に対応する \(2\) 頂点 \(A_v,B_v\) を用意し、以下のルールを定めて \(0\) か \(1\) を割り当てます。

• \(A_v\) と \(B_v\) に割り当てた重み（それぞれ \(W_{A_v},W_{B_v}\) などと表すことにする ）の和は \(W_v\) に等しい

このとき、
\(W_{u_m}+W_{v_m} \geq 3 \Leftrightarrow (W_{A_v},W_{B_u})=(1,1) \vee (W_{A_u},W_{B_v})=(1,1)\)
なので、これらの辺が禁止できればよいです。
\(W_{A_v}=0 \Leftrightarrow A_v \in S\)
\(W_{B_v}=0 \Leftrightarrow B_v \in T\)
となるようにグラフを構築すると最小カットに帰着することができます。

まとめ

構成したグラフは頂点数が \(O(N)\)、辺数が \(O(M)\) の二部グラフであるので、\(O(M\sqrt{N})\) で最大流を求めることができます。