スコアの定義を，次のように変更しても，答えは変わりません．

• 各頂点に，\(+1\) か \(-1\) の重みを割り振る． このとき，異なる重みの頂点が辺で結ばれていてはならない． 重み\(\times B_i\) の総和の最大値がスコアになる．

よって問題は，次のように変形できます．

• 各頂点に，\(+1\),\(delete\),\(-1\) のいずれかのタイプを割り当てる． タイプ \(+1\) と \(-1\) の頂点が隣接してはならない． 各頂点について，各タイプを割り当てる際のコストが，以下のように定まっている．コスト最小の割当を求めよ．

• \(B_i \geq 0\) の場合: タイプ \(+1,\ delete,\ -1\) のコストは，それぞれ \(0,\ B_i+A_i,\ 2B_i\) である．

• \(B_i< 0\) の場合: タイプ \(+1,\ delete,\ -1\) のコストは，それぞれ \(2|B_i|,\ |B_i|+A_i,\ 0\) である．

この問題は最小カット問題に帰着できます． 具体的には，超頂点\(S,T\) と，元のグラフの各頂点 \(i\) に対応する頂点 \(X_i,Y_i\) を作ります． そして，\(Y_i \rightarrow X_i\) に容量 \(inf\) の辺を張ります． すると，\((X_i,Y_i)\) がカットのどちら側にあるかで分類すると，\((S,S)\),\((S,T)\),\((T,T)\) の \(3\) 通りに分かれます． これらにそれぞれタイプ \(+1\),\(delete\),\(-1\) を割り当てると，上記の問題が最小カット問題に帰着できます．

最終的に得られるグラフは，\(O(N)\) 頂点 \(O(N+M)\) 辺のグラフです． Dinic法を用いると，このグラフの最小カットは \(O(N^2(N+M))\) 時間で求めることができます．