← 返回题目列表

AtCoder · abc461_g

G. 图问题2026

中文机器翻译题面 查看原题

分数: 625 点

问题陈述

有一个简单的无向图 N 顶点和 M 边缘。
顶点已编号 1 通过 N 且边缘已编号 1 通过 M;边缘 i 连接顶点 u_i 和 v_i.
分配非负整数权重 W_j 不大于 2026 到每个顶点 j 以满足以下条件:

  • W_{u_i}+W_{v_i} \leq 2026 对于每条边 i.

求所有顶点权重之和的最大可能值(即 \sum_{j=1}^{N}{W_j}).

约束

  • 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) 两两不同。
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N M  
u_1 v_1  
u_2 v_2  
\vdots  
u_M v_M  

输出

在一行上输出答案。


示例输入 1

3 2
1 2
2 3

示例输出 1

4052

通过分配权重 2026, 0, 2026 到顶点 1, 2, 3,所有顶点权重之和分别变为 4052,而且不可能让它变大,所以答案是 4052.


示例输入 2

4 6
1 2
2 3
1 4
2 4
1 3
3 4

示例输出 2

4052

示例输入 3

2 1
1 2

示例输出 3

2026