Original proposer: admin

This problem has two approaches of observation, both leading to a similar graph constructions. We will introduce both.

1. Ad-hoc construction of a bipartite graph

Prepare \(2N\) vertices \(A_1,A_2,\dots,A_N,B_1,B_2,\dots,B_N\).
For \(m=1,2,\dots,M\), add edges from \(A_{u_m}\) to \(B_{v_m}\) and from \(A_{v_m}\) to \(B_{u_m}\).
Take a maximum independent set \(MIS\) of this graph. We will show that the answer is \(1013 \times |MIS|\).

Let
\(f(v)=\begin{cases}1(v \in MIS)\\0 (v\notin MIS).\end{cases}\)
For \(i=1,2,\dots,N\), assign an edge as \(W_i=1013 \times (f(A_i)+f(B_i))\).
For \(m=1,2,\dots,M\), \(f(A_{u_m})+f(B_{v_m})\) and \(f(A_{v_m})+f(B_{u_m})\) are both at most \(1\), so \((W_{u_m}+W_{v_m}) \leq 1013 \times (1+1)=2026\). Thus the answer is at least \(1013 \times |MIS|\)

Let \(IV_1,IV_2,\dots,IV_K\) be the isolated vertices of the constructed graph. After removing them, take a minimum edge cover \(MEC\).
Since the constructed graph is a bipartite graph, \(|MIS|=|MEC|+K\).
By definition of minimum edge cover,
\(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|,\)
so \(\sum_{i=1}^{N}{W_i} \leq 1013 \times |MIS|\).

Hence, the answer has been proved to be \(1013 \times |MIS|\).

2. Half-integrality (Linear Programming) relaxation

Extend the domain of weights from integers to real numbers. Define
\(P_-=\{v|0 \lt W_v \lt 1013\},\)
\(P_+=\{v|2026 \gt W_v \gt 1013\}.\)
Among the solutions that maximize \(\sum_{i=1}^{N}{W_i}\), take one that minimizes \(|P_- \cup P_+|\).

Assume that
\(P_- \cup P_+ \neq \emptyset\).
Let \(d=\min(1013-\max(P_-),\min(P_+)-1013)\). If \(|P_+| \lt |P_-|\), we can make \(\sum_{i=1}^{N}{W_i}\) larger by subtracting \(d\) from \(W_v\) for each \(v\) in \(P_+\) and adding \(d\) to \(W_v\) for each \(v\) in \(P_-\), so \(|P_+| \geq |P_-|\).
Likewise, we also see that \(|P_+| \leq |P_-|\); thus \(|P_+| = |P_-|\).
By subtracting \(d\) from \(W_v\) for each \(v\) in \(P_+\) and adding \(d\) to \(W_v\) for each \(v\) in \(P_-\), one can make \(|P_- \cup P_+|\) smaller, which is a contradiction.
Thus, \(P_- \cup P_+ = \emptyset\), and we may assume that \(W_v \in \{0,1013,2026\}\).
By dividing \(W_v\) by \(1013\), the problem is reduced to assigning \(0\), \(1\), or \(2\) to each vertex.
Now it is sufficient to solve a cost minimization problem subject to:

• Assigning \(w_v\) to \(v\) costs \(-W_v\).
• Being \(W_{u_m}+W_{v_m} \geq 3\) incurs cost \(\infty\).

This cost is submodular, so it can be boiled down to a minimum-cut problem.

Summary

The constructed graph has \(O(N)\) vertices and \(O(M)\) edges, so the maximum flow can be found in \(O(M\sqrt{N})\) time.