#P9562. [SDCPC 2023] Matching
[SDCPC 2023] Matching
题目描述
Given an integer sequence of length , we construct an undirected graph from the sequence. More precisely, for all , if , there will be an undirected edge in connecting vertices and . The weight of the edge is .
Find a matching of so that the sum of weight of all edges in the matching is maximized, and output this maximized sum.
Recall that a matching of an undirected graph means that we choose some edges from the graph such that any two edges have no common vertices. Specifically, not choosing any edge is also a matching.
输入格式
There are multiple test cases. The first line of the input contains an integer indicating the number of test cases. For each test case:
The first line contains an integer () indicating the length of the sequence.
The second line contains integers () indicating the sequence.
It's guaranteed that the sum of of all test cases will not exceed .
输出格式
For each test case output one line containing one integer indicating the maximum sum of weight of all edges in a matching.
3
9
3 -5 5 6 7 -1 9 1 2
3
-5 -4 -3
3
1 10 100
30
0
0
提示
For the first sample test case, the optimal choice is to choose the three edges connecting vertex and , vertex and , and finally vertex and . The sum of weight is .
For the second sample test case, as all edges have negative weights, the optimal matching should not choose any edge. The answer is .
For the third sample test case, as there is no edge in the graph, the answer is .