分数: 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