给新人来个帖子 要来水积分来这里3

【表情】

水水水水水水水水水水

【表情】

水水水水水水水水水水

【表情】

水水水水水水水水水水

【表情】

水水水水水水水水水水

【表情】

水水水水水水水水水水

【表情】

水水水水水水水水水水

【表情】

水水水水水水水水水水

【表情】

水水水水水水水水水水

FandaP

【表情】 发表于 2025-11-13 12:14
水水水水水水水水水水

因为我的帖子还真来水了吗（）

chuge

我荡起双桨

chuge

我推开波浪

chuge

海面当应这美丽的白塔

chuge

四周环绕着绿树红墙

【表情】

# P14361 [CSP-S 2025] 社团招新

## 题目描述

小 L 是学校算法协会的成员。在今年的学校社团招新中，小 L 一共招收了 $n$ 个新成员，其中 $n$ 为**偶数**。现在小 L 希望将他们分到协会不同的部门。

算法协会共设有三个部门，其中第 $i$ ($1 \leq i \leq n$) 个新成员对第 $j$ ($1 \leq j \leq 3$) 个部门的满意度为 $a_{i,j}$。定义一个分配方案的满意度为所有新成员对分配到的部门的满意度之和，也就是说，若将第 $i$ ($1 \leq i \leq n$) 个新成员分配到了第 $d_i \in \{1,2,3\}$ 个部门，则该分配方案的满意度为 $\sum_{i=1}^{n} a_{i,d_i}$。

小 L 不希望某一个部门的新成员数量过多。具体地，他要求在分配方案中，不存在一个部门被分配多于 $\frac{n}{2}$ 个新成员。你需要帮助小 L 求出，满足他要求的分配方案的满意度的最大值。

## 输入格式

本题包含多组测试数据。

输入的第一行包含一个正整数 $t$，表示测试数据组数。

接下来依次输入每组测试数据，对于每组测试数据：

- 第一行包含一个正整数 $n$，表示新成员的数量。
- 第 $i+1$ ($1 \leq i \leq n$) 行包含三个非负整数 $a_{i,1}, a_{i,2}, a_{i,3}$，分别表示第 $i$ 个新成员对第 $1,2,3$ 个部门的满意度。

## 输出格式

对于每组测试数据，输出一行一个非负整数，表示满足小 L 要求的分配方案的满意度的最大值。

## 输入输出样例 #1

### 输入 #1

```
3
4
4 2 1
3 2 4
5 3 4
3 5 1
4
0 1 0
0 1 0
0 2 0
0 2 0
2
10 9 8
4 0 0
```

### 输出 #1

```
18
4
13
```

## 说明/提示

### 【样例 1 解释】

该样例共包含三组测试数据。

对于第一组测试数据，可以将四个新成员分别分配到第 $1,3,1,2$ 个部门，则三个部门的新成员数量分别为 $2,1,1$，均不超过 $\frac{4}{2} = 2$，满意度为 $4 + 4 + 5 + 5 = 18$。

对于第二组测试数据，可以将四个新成员分别分配到第 $1,1,2,2$ 个部门，则三个部门的新成员数量分别为 $2,2,0$，均不超过 $\frac{4}{2} = 2$，满意度为 $0 + 0 + 2 + 2 = 4$。

对于第三组测试数据，可以将两个新成员分别分配到第 $2,1$ 个部门，则三个部门的新成员数量分别为 $1,1,0$，均不超过 $\frac{2}{2} = 1$，满意度为 $9 + 4 = 13$。

### 【样例 2】

见选手目录下的 $\textbf{\textit{club/club2.in}}$ 与 $\textbf{\textit{club/club2.ans}}$。

该样例满足测试点 $3,4$ 的约束条件。

### 【样例 3】

见选手目录下的 $\textbf{\textit{club/club3.in}}$ 与 $\textbf{\textit{club/club3.ans}}$。

该样例满足测试点 $5 \sim 8$ 的约束条件。

### 【样例 4】

见选手目录下的 $\textbf{\textit{club/club4.in}}$ 与 $\textbf{\textit{club/club4.ans}}$。

该样例满足测试点 $9$ 的约束条件。

### 【样例 5】

见选手目录下的 $\textbf{\textit{club/club5.in}}$ 与 $\textbf{\textit{club/club5.ans}}$。

该样例满足测试点 $15,16$ 的约束条件。

### 【数据范围】

对于所有测试数据，保证：

- $1 \leq t \leq 5$;
- $2 \leq n \leq 10^5$，且 $n$ 为偶数;
- 对于所有 $1 \leq i \leq n$，$1 \leq j \leq 3$，均有 $0 \leq a_{i,j} \leq 2 \times 10^4$。

::cute-table{tuack}

| 测试点编号 | $n=$ | 特殊性质 |
| :--: | :--: | :--: |
| $1$ | $2$ | 无 |
| $2$ | $4$ | ^ |
| $3, 4$ | $10$ | ^ |
| $5 \sim 8$ | $30$ | ^ |
| $9$ | $200$ | B |
| $10, 11$ | ^ | 无 |
| $12$ | $10^5$ | A |
| $13, 14$ | ^ | B |
| $15, 16$ | ^ | C |
| $17 \sim 20$ | ^ | 无 |


特殊性质 A：对于所有 $1 \leq i \leq n$，均有 $a_{i,2} = a_{i,3} = 0$。

特殊性质 B：对于所有 $1 \leq i \leq n$，均有 $a_{i,3} = 0$。

特殊性质 C：对于所有 $1 \leq i \leq n$，$1 \leq j \leq 3$，$a_{i,j}$ 均在 $[0, 2 \times 10^4]$ 中独立均匀随机生成。

【表情】

# P14362 [CSP-S 2025] 道路修复

## 题目背景

由于评测机性能差异，本题时限提升 1 秒。

## 题目描述

C 国的交通系统由 $n$ 座城市与 $m$ 条连接两座城市的双向道路构成，第 $i$ ($1 \leq i \leq m$) 条道路连接城市 $u_i$ 和 $v_i$。**任意两座城市都能通过若干条道路相互到达。**

然而，近期由于一场大地震，所有 $m$ 条道路都被破坏了，修复第 $i$ ($1 \leq i \leq m$) 条道路的费用为 $w_i$。与此同时，C 国还有 $k$ 个准备进行城市化改造的乡镇。对于第 $j$ ($1 \leq j \leq k$) 个乡镇，C 国对其进行城市化改造的费用为 $c_j$。在城市化改造完第 $j$ ($1 \leq j \leq k$) 个乡镇后，可以在这个乡镇与原来的 $n$ 座城市间建造若干条道路，其中在它与第 $i$ ($1 \leq i \leq n$) 座城市间建造一条道路的费用为 $a_{j,i}$。C 国可以在这 $k$ 个乡镇中选择**任意多个**进行城市化改造，也可以不选择任何乡镇进行城市化改造。

为尽快恢复城市间的交通，C 国政$ $府希望以最低的费用将**原有**的 $n$ 座城市两两连通，也即任意两座原有的城市都能通过若干条修复或新建造的道路相互到达。你需要帮助他们求出，将原有的 $n$ 座城市两两连通的最小费用。

## 输入格式

输入的第一行包含三个非负整数 $n, m, k$，分别表示原有的城市数量、道路数量和准备进行城市化改造的乡镇数量。

输入的第 $i+1$ ($1 \leq i \leq m$) 行包含三个非负整数 $u_i, v_i, w_i$，表示第 $i$ 条道路连接的两座城市与修复该道路的费用。

输入的第 $j+m+1$ ($1 \leq j \leq k$) 行包含 $n+1$ 个非负整数 $c_j, a_{j,1}, a_{j,2}, \ldots, a_{j,n}$，分别表示将第 $j$ 个乡镇进行城市化改造的费用与在该乡镇与原有的城市间建造道路的费用。

## 输出格式

输出一行一个非负整数，表示将原有的 $n$ 座城市两两连通的最小费用。

## 输入输出样例 #1

### 输入 #1

```
4 4 2
1 4 6
2 3 7
4 2 5
4 3 4
1 1 8 2 4
100 1 3 2 4
```

### 输出 #1

```
13
```

## 说明/提示

### 【样例 1 解释】

C 国政$ $府可以选择修复第 $3$ 条和第 $4$ 条道路，然后将第 $1$ 个乡镇进行城市化改造，并建造它与第 $1,3$ 座城市间的道路，总费用为 $5 + 4 + 1 + 1 + 2 = 13$。可以证明，不存在比 $13$ 更小的费用能使原有的 $4$ 座城市两两连通。

### 【样例 2】

见选手目录下的 $\textbf{\textit{road/road2.in}}$ 与 $\textbf{\textit{road/road2.ans}}$。

该样例满足测试点 $11,12$ 的约束条件。

### 【样例 3】

见选手目录下的 $\textbf{\textit{road/road3.in}}$ 与 $\textbf{\textit{road/road3.ans}}$。

该样例满足测试点 $13,14$ 的约束条件。

### 【样例 4】

见选手目录下的 $\textbf{\textit{road/road4.in}}$ 与 $\textbf{\textit{road/road4.ans}}$。

该样例满足测试点 $15,16$ 的约束条件。

### 【数据范围】

对于所有测试数据，保证：

- $1 \leq n \leq 10^4$，$1 \leq m \leq 10^6$，$0 \leq k \leq 10$；
- 对于所有 $1 \leq i \leq m$，均有 $1 \leq u_i, v_i \leq n$，$u_i \neq v_i$ 且 $0 \leq w_i \leq 10^9$；
- 对于所有 $1 \leq j \leq k$，均有 $0 \leq c_j \leq 10^9$；
- 对于所有 $1 \leq j \leq k$，$1 \leq i \leq n$，均有 $0 \leq a_{j,i} \leq 10^9$；
- 任意两座原有的城市都能通过若干条原有的道路相互到达。

::cute-table{tuack}

| 测试点编号 | $n \leq$ | $m \leq$ | $k \leq$ | 特殊性质 |
| :--: | :--: | :--: | :--: | :--: |
| $1 \sim 4$ | $10^4$ | $10^6$ | $0$ | 无 |
| $5, 6$ | $10^3$ | $10^5$ | $5$ | A |
| $7, 8$ | ^ | ^ | ^ | 无 |
| $9, 10$ | ^ | $10^6$ | ^ | A |
| $11, 12$ | ^ | ^ | ^ | 无 |
| $13, 14$ | ^ | ^ | $10$ | A |
| $15, 16$ | ^ | ^ | ^ | 无 |
| $17, 18$ | $10^4$ | ^ | $5$ | A |
| $19, 20$ | ^ | ^ | ^ | 无 |
| $21 \sim 25$ | ^ | ^ | $10$ | ^ |

特殊性质 A：对于所有 $1 \leq j \leq k$，均有 $c_j = 0$ 且均存在 $1 \leq i \leq n$ 满足 $a_{j,i} = 0$。