G. 图问题 2026 · AC 题库

AtCoder Beginner Contest 461

图问题 2026

Graph Problem 2026

AtCoder

⌀ 2391

原题

← F→

图问题 2026AI (CI翻译)

Problem Statement

题目描述

AI (CI翻译)

There is a simple undirected graph with $N$ vertices and $M$ edges. The vertices are numbered $1$ through $N$ and the edges are numbered $1$ through $M$ ; edge $i$ connects vertices $u_i$ and $v_i$ . Assign a non-negative integer weight $W_j$ not greater than $2026$ to each vertex $j$ so that the following condition is satisfied:

有一个包含 $N$ 个顶点和 $M$ 条边的简单无向图。顶点编号为 $1$ 至 $N$ ，边编号为 $1$ 至 $M$ ；第 $i$ 条边连接顶点 $u_i$ 和 $v_i$ 。请为每个顶点 $j$ 分配一个不超过 $2026$ 的非负整数权重 $W_j$ ，使得满足以下条件：AI (CI翻译)

$W_{u_i}+W_{v_i} \leq 2026$ for each edge $i$ .

对于每条边 $i$ ，均有 $W_{u_i}+W_{v_i} \leq 2026$ 。

AI (CI翻译)

Find the maximum possible value of the sum of all vertex weights (that is, $\sum_{j=1}^{N}{W_j}$ ).

求所有顶点权重之和（即 $\sum_{j=1}^{N}{W_j}$ ）的最大可能值。AI (CI翻译)

Constraints

约束条件

AI (CI翻译)

$1 \leq N \leq 5 \times 10^4$
$0 \leq M \leq 5 \times 10^4$
$1 \leq u_i \lt v_i \leq N$
$(u_1,v_1),(u_2,v_2),\dots,(u_M,v_M)$ are pairwise distinct.
All input values are integers.

$1 \leq N \leq 5 \times 10^4$
$0 \leq M \leq 5 \times 10^4$
$1 \leq u_i \lt v_i \leq N$
$(u_1,v_1),(u_2,v_2),\dots,(u_M,v_M)$ 两两不同。
所有输入值均为整数。

AI (CI翻译)

Input

输入格式

AI (CI翻译)

The input is given from Standard Input in the following format:

输入从标准输入中按以下格式给出：AI (CI翻译)

N M
u_1 v_1
u_2 v_2
\vdots
u_M v_M

N M
u_1 v_1
u_2 v_2
\vdots
u_M v_M

AI (CI翻译)

Output

输出格式

AI (CI翻译)

Output the answer on a single line.

在一行中输出答案。AI (CI翻译)

样例

Input #1

3 2
1 2
2 3

Output #1

By assigning weights $2026, 0, 2026$ to vertices $1, 2, 3$, respectively, the sum of all vertex weights becomes $4052$, and it is impossible to make it larger, so the answer is $4052$.

Input #2

Output #2

Input #3

2 1
1 2

Output #3

题目信息

题号

abc461_g

所属比赛

AtCoder Beginner Contest 461

时间限制

4 s

内存限制

1024 MB

题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。