Perfect matching 最佳匹配问题

Question

Problem Description
Given the complete bipartite graph. Each part of this graph has N vertices, i.e. the graph is balanced. An integer number (called a weight) assigns to each vertex. The weight of the edge is defined as the product of weights of vertices which connected by this edge.
It is well known, a matching in a graph is a set of edges without common vertices. A matching is perfect, if it covers all vertices of a graph.
Write a program to find a perfect match of the given bipartite graph with the maximal weight of the matching edges minimal.

Input
The input consists of multiple cases.
For each testcase,there will be exactly three lines;
The first line contains one integer number N (1 ≤ N ≤ 105). The second line consist of N integer numbers, not exceeded 109 by absolute value. The i-th number in line denotes a weight of i-th vertex of first part of a graph. In the third line, weights of vertices of second part are presented.

Output
The answer specified above.

Sample Input
3
1 2 3
9 10 11

Sample Output
27

Answer 1

让阿豪来帮你解答，本回答参考chatgpt3.5编写提供，如果还有疑问可以评论或留言

```python def perfect_matching(N, weights1, weights2):

weights1.sort(reverse=True)
weights2.sort(reverse=True)
total_weight = 0
for i in range(N):
    total_weight += weights1[i] * weights2[i]
return total_weight

Read input

T = int(input()) for _ in range(T): N = int(input()) weights1 = list(map(int, input().split())) weights2 = list(map(int, input().split())) result = perfect_matching(N, weights1, weights2) print(result)

Sample Input

3 1 2 3 9 10 11

Sample Output

27