CCF GESP 2025年6月认证 C++ 7级
题目描述
给定由 $n$ 个结点与 $m$ 条边构成的简单无向图 $G$，结点依次以 $1,2,\dots,n$ 编号。简单无向图意味着 $G$ 中不包含重边与自环。$G$ 的**线图** $L(G)$ 通过以下方式构建：
- 初始时线图 $L(G)$ 为空。
- 对于无向图 $G$ 中的一条边，在线图 $L(G)$ 中加入与之对应的一个结点。
- 对于无向图 $G$ 中两条不同的边 $(u_1,v_1),(u_2,v_2)$，若存在 $G$ 中的结点同时连接这两条边（即 $u_1,v_1$ 之一与 $u_2,v_2$ 之一相同），则在线图 $L(G)$ 中加入一条无向边，连接 $(u_1,v_1),(u_2,v_2)$ 在线图中对应的结点。
请你求出线图 $L(G)$ 中所包含的无向边的数量。
输入格式
第一行，两个正整数 $n,m$，分别表示无向图 $G$ 中的结点数和边数。
接下来 $m$ 行，每行两个正整数 $u_i,v_i$，表示 $G$ 中连接 $u_i,v_i$ 的一条无向边。
输出格式
输出共一行，一个整数，表示线图 $L(G)$ 中所包含的无向边的数量。
样例说明
样例 1
5 4
1 2
2 3
3 1
4 53
样例 2
5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 530数据范围
对于 60% 的测试点，保证 $1 \le n \le 500$，$1 \le m \le 500$ 。
对于所有测试点，保证 $1 \le n \le 10^5$，$1 \le m \le 10^5$ 。
题目描述
小 A 准备了 $n$ 种食材用来制作料理，这些食材依次以 $1,2,\dots,n$ 编号，第 $i$ 种食材的酸度为 $a_i$，甜度为 $b_i$。对于每种食材，小 A 可以选择将其放入料理，或者不放入料理。料理的酸度 $A$ 为放入食材的酸度之和，甜度 $B$ 为放入食材的甜度之和。如果料理的酸度和甜度相等，那么料理的调味是平衡的。
过于清淡的料理并不好吃，因此小 A 想在满足料理调味平衡的前提下，合理选择食材，最大化料理的酸度与甜度之和。你能帮他求出在调味平衡的前提下，料理酸度与甜度之和的最大值吗？
输入格式
第一行，一个正整数 $n$，表示食材种类数量。
接下来 $n$ 行，每行两个正整数 $a_i,b_i$，表示食材的酸度和甜度。
输出格式
输出共一行，一个整数，表示在调味平衡的前提下，料理酸度与甜度之和的最大值。
样例说明
样例 1
3
1 2
2 4
3 28样例 2
5
1 1
2 3
6 1
8 2
5 72数据范围
对于 $40\%$ 的测试点，保证 $1 \le n \le 10$，$1 \le a_i,b_i \le 10$。
对于另外 $20\%$ 的测试点，保证 $1 \le n \le 50$，$1 \le a_i,b_i \le 10$。
对于所有测试点，保证 $1 \le n \le 100$，$1 \le a_i,b_i \le 500$。