以下页面来自赛事官方发布的原题PDF,已完整保存并渲染到本地。


可复制的 PDF 提取文本
Problem B
Attraction Score
Time limit: 4 seconds
There are n cities, numbered from 1 to n, in the fictional country of Manteiv. We can consider these cities to be on a
flat plane with a 2D coordinate system, where city i is at coordinates (xi, yi). No two cities are located at the same
position.
There are m highways, numbered from 1 to m, each of which is a line segment with two different cities as its endpoints
and has a number of attraction points alongside it. Specifically, highway j has aj attraction points and connects cities
uj and vj as its endpoints. Having intersections on highways causes traffic jams, and building a highway on top of
another highway costs a lot of money. Therefore, it is guaranteed that
• no two highways intersect at any point other than at a city,
• no highway passes through a city other than its two endpoints, and
• there is at most one highway connecting each pair of cities.
The Manteiv Ministry of Tourism would like to choose a subset of cities as tourist attractions. Intuitively, the ministry
would like many pairs of chosen cities to be connected by a highway with many attraction points. Formally, the
attraction score of a non-empty subset of cities S is defined as follows:
• For every pair of integers (a, b) where a < b, cities a and b are in S, and they are connected by a highway, add
the number of attraction points on the highway to the score.
• Let f(S) be the number of pairs of integers (a, b) where a < b, cities a and b are in S, and they are not connected
by a highway. The score incurs a penalty (negative) score of 106 multiplied by the square of f(S). In other
words, subtract 106 × f(S)2 from the score.
For example, let n = 3, cities 1 and 2 be connected by a highway with 10 attraction points, cities 2 and 3 be connected
by a highway with 20 attraction points, and cities 1 and 3 not be connected by a highway.
• The attraction score of the subset of cities {1} is 0.
• The attraction score of the subset of cities {1, 2} is 10 −106 × 02 = 10.
• The attraction score of the subset of cities {2, 3} is 20 −106 × 02 = 20.
• The attraction score of the subset of cities {1, 2, 3} is 10 + 20 −106 × 12 = −999 970.
As an advisor to the ministry, you would like to find the maximum attraction score among all possible non-empty
subsets of cities S.
Input
The first line of input contains two integers n and m (1 ≤n ≤100 000; 0 ≤m ≤300 000). Each of the next n lines
contains two integers. The i-th line contains xi and yi (0 ≤xi, yi ≤109). Each of the next m lines contains three
integers. The j-th line contains uj, vj, and aj (1 ≤uj < vj ≤n; 0 ≤aj ≤106). The highways are guaranteed to
satisfy the conditions in the problem statement.
ICPC Asia Pacific Championship 2024 Problem B: Attraction Score
Output
Output an integer representing the maximum attraction score among all possible non-empty subsets of cities S.
Sample Input #1 Sample Output #1
3 2 20
0 0
0 1
1 0
1 2 10
2 3 20
Explanation for the sample input/output #1
This sample is the example given in the problem statement above. The subset of cities {2, 3} gives the highest attraction
score of 20.
Sample Input #2 Sample Output #2
3 3 60
0 0
0 1
1 0
1 2 10
2 3 20
1 3 30
Explanation for the sample input/output #2
The cities and highways are illustrated by Figure B.1. By choosing cities 1, 2, and 3 in S, the attraction score would
be 10 + 20 + 30 −106 × 02 = 60.
1 City 2
A2 = 20
A1 = 10
0 City 1 A3 = 30 City 3
0 1
Figure B.1: Illustration of sample input #2.
ICPC Asia Pacific Championship 2024 Problem B: Attraction Score