P2128 The Battle of Red Cliffs

At the Battle of Red Cliffs, Huang Gai (Huang Gai) pretended to defect to Cao Cao’s fleet with ships loaded with reeds and oil. Under Pang Tong’s “chained ships” stratagem, Cao Cao’s warships were connected by iron chains. No two ships were at the same position, and no chains intersected one another or passed through any ship. Each ship had a given strategic value. To ensure the destructive effect, Huang Gai must guarantee that every pair among the ignited Cao Cao ships is directly connected by an iron chain. He hopes to find a plan to ignite ships whose total value is as large as possible.

The first line contains numbers $N$, $M$, the number of warships and the number of iron chains. The next $N$ lines, the $i$-th line contains $1$ number $V_i$, the strategic value of the $i$-th warship. The next $M$ lines, the $i$-th line contains $2$ numbers $S_i$, $T_i$, indicating the two ships connected by an iron chain. It is guaranteed that this is a valid fleet arrangement.

Output one number, the maximum total value of warships that can be destroyed.

- Constraints - For $50\%$ of the testdata, $N$, $M \le 10$. - For $100\%$ of the testdata, $N \le 450$, $M \le 900$, $V_i \le 6000$. - Note - Every sentence in the statement (except the first paragraph) is relevant. Translated by ChatGPT 5