P16442 [XJTUPC 2026] Computer Lab Allocation

To reduce the risk of cheating in programming contests, the school needs to assign $n$ contestants to $k$ computer labs for the contest. It is known that some contestants are relatively familiar with each other. We use a weighted undirected graph $G=(V,E)$ to describe these relationships: - Each vertex represents a contestant. - Each edge represents that there is some relationship between two contestants. - The edge weight is a positive integer indicating how close their relationship is. A larger weight means they are more familiar with each other. - The graph $G$ is a simple graph with no self-loops and no multiple edges. If the total relationship strength among contestants in the same lab is too high, it will increase the pressure on proctors. For a certain lab, the sum of the weights of all edges whose both endpoints are assigned to this lab is called the **risk value** of this lab. Let the sum of all edge weights in the whole graph be $S = \sum\limits_{e \in E} w_e$, where $w_e$ denotes the weight of edge $e$. The school requires that the **sum of the risk values of all labs** must not exceed $\left\lceil \frac{S}{k} \right\rceil$. Now you need to determine whether there exists an assignment such that: - Each contestant is assigned to exactly one lab. - The sum of the risk values of all labs does not exceed $\left\lceil \frac{S}{k} \right\rceil$. If it exists, output one assignment that satisfies the requirements. If there are multiple valid assignments, output any one. Note: It is allowed that a lab has no contestants assigned to it. The graph $G$ is not guaranteed to be connected.

The first line contains three integers $n, m$ and $k$ ($1 \le k \le n \le 5\times 10^5, 0 \le m \le 5\times 10^5$), separated by spaces, representing the number of contestants, the number of relationships, and the number of computer labs. The next $m$ lines each contain three integers $u, v$ and $w$ ($1 \le u,v \le n, u \ne v, 1 \le w \le 10^9$), separated by spaces, indicating an undirected edge of weight $w$ between contestant $u$ and contestant $v$. It is guaranteed that there are no multiple edges in the input graph.

If there is no assignment that satisfies the requirements, output one line containing only the string $\tt{No}$. Otherwise output two lines: - The first line contains the string $\tt{Yes}$. - The second line contains $n$ integers $a_1,a_2,\cdots,a_n$ ($1 \le a_i \le k$), separated by spaces, where $a_i$ indicates that contestant $i$ is assigned to lab $a_i$. If there are multiple valid assignments, output any one.

Translated by ChatGPT 5