P4643 [CTT] Ali and Peach's Game

Ali and Peach are playing a game on a weighted graph $G=(V,E)$. Let the weight of a vertex be $w(v)$, and the weight of an edge be $c(e)$. The rules are: 1. Ali and Peach take turns coloring vertices in the graph. Ali colors a vertex red, and Peach colors a vertex pink. A vertex that has already been colored cannot be colored again, and in each turn, exactly one vertex must be colored. 2. To ensure fairness, the number of vertices $N$ is even. 3. After $\frac{N}{2}$ rounds, each player obtains a set of vertices. For a vertex set $S$, the score is $$\sum_{v \in S}w(v) + \sum_{e=(u,v)\in E \land u,v\in S}c(e)$$ Since Ali lost Rock-Paper-Scissors to Peach, Peach colors first. Both players want their own score to exceed the other’s, and the larger the difference, the better. Assuming both players use optimal strategies, find the final value of Peach’s score minus Ali’s score.

The first line contains two positive integers $N$ and $M$, representing the number of vertices and edges of the graph $G$, where $N$ is guaranteed to be even. The next $N+M$ lines follow. The first $N$ lines each contain one integer $w$. The $k$-th of these lines gives the weight of vertex $k$. The next $M$ lines each contain three integers $a,b,c$ separated by spaces, describing an edge between vertices $a$ and $b$ with weight $c$.

Output exactly one integer, which is Peach’s score minus Ali’s score.

Constraints and notes: For $40\%$ of the testdata, $1 \le N \le 16$. For $100\%$ of the testdata, $1 \le N \le 10000$, $1 \le M \le 100000$, $-10000 \le w , c \le 10000$. Translated by ChatGPT 5