P3872 [TJOI2010] Movie Buff

Xiao A is a movie buff. He has collected hundreds of movies and plans to pick some to watch during the holidays. Based on his taste and online information, he assigned to each movie $X$ a score $v_X$ indicating how much he likes it. The score range is from $-1000$ to $1000$, and a larger score means he likes it more. Each time Xiao A watches a movie $X$, his experience increases by $v_X$. In addition, because some movies belong to the same series (for example, the famous Terminator series, The Matrix series, etc.), if Xiao A watches an earlier one but not a later one, he will feel uncomfortable. More precisely, for any two distinct movies $X, Y$, there may be a dependency value $d_{X,Y}$, meaning that if Xiao A watches $X$ but not $Y$, his experience will decrease by $d_{X,Y}$. (Note that the viewing order does not matter; as long as both are watched, there is no penalty.) Now he wants to select some movies to watch to maximize the total experience. If he cannot obtain a positive experience, output $0$.

- The first line contains two integers: the total number of movies $N$ and the number of dependency relations $M$. - The second line contains $N$ space-separated numbers, the scores for each movie. - Each of the next $M$ lines contains three integers $X, Y, d_{X,Y}$, representing a dependency relation. - Each ordered pair $(X, Y)$ appears at most once. $1 \le X, Y \le N$.

Output one integer, the maximum experience Xiao A can obtain.

If Xiao A only watches movie $1$, the experience is $100 - 49 = 51$. If he only watches movie $2$, the experience is $-50 - 10 = -60$. If he watches both, the experience is $100 + (-50) = 50$. Therefore, he should only watch movie $1$. Constraints: - For $20\%$ of the testdata, $1 \le N \le 15$. - For $100\%$ of the testdata, $1 \le N \le 100$, $-1000 \le v_X \le 1000$, $0 < d_{X,Y} \le 1000$. - Time limit per test point is 1 second. Translated by ChatGPT 5