| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 13 | 8 | 8 | 61.538% |
The city of “문해프” consists of $N$ buildings and $N - 1$roads, forming a tree structure(meaning that every pair of buildings is connected by exactly one simple path, and there are no cycles.). All roads are bidirectional and have their own lengths.
The newly appointed mayor of “문해프” City plans to divide the city into $K$ regions by removing $K-1$ roads. (if $K = 1,ドル a single region covers the entire city.) Then, one Network Station will be built in each region to facilitate communication among the buildings within that region.
Each region $R$ contains multiple buildings. The communication complexity of region $R$ is defined as $ \sum_{i,j\in R, i<j} \operatorname{dist}(i,j) ,ドル where the sum runs over all unordered pairs of distinct buildings in $R$. In other words, the communication complexity of a region is the total sum of distances between all pairs of buildings in that region.
The mayor of “문해프” City wants to minimize the maximum communication complexity among all regions. Find the minimum possible value of this maximum communication complexity when the city is divided optimally.
The first line contains two integers $N$ and $K,ドル the number of buildings and the number of regions to divide the city into. $(K \leq N \leq 100,000,円 K \in \{1,2\})$
Each of the next $N-1$ lines contains three integers $a_i,ドル $b_i,ドル and $c_i,ドル indicating that there is a bidirectional road between buildings $a_i$ and $b_i$ with length $c_i$. $(1 \leq c_i \leq 100)$
It is guaranteed that the given graph forms a tree.
Print a single integer: the minimum possible value of the maximum communication complexity among all regions.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 50 | 1ドル \leq N \leq 400, K = 1$ |
| 2 | 10 | 1ドル \leq N \leq 2,000,円 K = 1$ |
| 3 | 10 | 1ドル \leq N \leq 100,000,円 K = 1$ |
| 4 | 10 | $K \leq N \leq 400, K \in \{1,2\}$ |
| 5 | 10 | $K \leq N \leq 2,000,円 K \in \{1,2\}$ |
| 6 | 10 | $K \leq N \leq 100,000,円 K \in \{1,2\}$ |
4 1 2 1 1 2 3 2 2 4 4
21
Since $K = 1,ドル Region 1 represents the entire city. The communication complexity of Region 1 is dist(1, 2) + dist(1, 3) + dist(1, 4) + dist(2, 3) + dist(2, 4) + dist(3, 4) = 1 +たす 3 +たす 5 +たす 2 +たす 4 +たす 6 =わ 21.
This example satisfies the conditions of all subtasks.
5 2 1 2 1 1 3 2 1 4 10 4 5 3
6
The communication complexity of Region 1 is dist(1, 2) + dist(1, 3) + dist(2, 3) = 6.
The communication complexity of Region 2 is dist(4, 5) = 3.
In this example, dividing the regions as shown in the figure is optimal, and the answer is max(3, 6) = 6.
This example satisfies the conditions of Subtask 4, 5, and 6.
1 1
0
The communication complexity of Region 1 is 0.
This example satisfies the conditions of all subtasks.
University > 서강대학교 > CSE4152 문제해결프로그래밍실습 > 2025-2학기 중간고사 코딩 테스트 5번