Using the following as the definition of scores doesn’t change the answer:

• Assign to each vertex either \(+1\) or \(-1\) as its weight. Here, vertices with different weights cannot be connected by edges. The score is the maximum possible sum of \((\)Vertex \(i\)’s weight\() \times B_i\).

Therefore, the problem can be reduced to the following problem:

• Assign to each vertex one of type \(+1\), type \(\mathrm{deleted}\) or type \(-1\). Type \(+1\) vertices and type \(-1\) vertices cannot be adjacent. For each vertex, the cost of assigning each type to it is defined as follows. Find the minimum possible cost of an assignment.

• If \(B_i \geq 0\) : the cost of assigning types \(+1,\ \mathrm{deleted},\ -1\) is \(0,\ B_i+A_i,\ 2B_i\) respectively.

• \(B_i< 0\) : the cost of assigning types \(+1,\ \mathrm{deleted},\ -1\) is \(2|B_i|,\ |B_i|+A_i,\ 0\) respectively.

This problem can be reduced to the minimum cut problem. Specifically, let us have two terminal vertices, \(S\) and \(T\), and vertices \(X_i\) and \(Y_i\) corresponding to each vertex \(i\) in the original graph. After that, add an edge \(Y_i \to X_i\) with capacity \(\infty\). In this network, let us pick an arbitrary cut. On which side of the cut \(X_i\) and \(Y_i\) are has three possibilities: \((S,S)\), \((S,T)\) or \((T,T)\) where \(S\) and \(T\) denotes the source’s side to the sink’s side respectively. By assigning types \(+1,\ \mathrm{deleted}\) and \(-1\) to these three, the aforementioned problem is reduced to the minimum cut problem.

The resulting flow network has \(O(N)\) vertices and \(O(N + M)\) edges. By using Dinic’s algorithm, the minimum cut of this flow network can be found in \(O(N^2 (N+M))\)-time.