题目理解

城市 $C$ 中有 $n$ 个交叉路口，$m$ 条双向道路连接这些路口，每条道路有一个分值 $c$。市长希望对部分道路进行改造，要求：

1. 改造后的道路使所有路口连通；
2. 在满足要求 1 的情况下，改造的道路数量尽量少；
3. 在满足要求 1、2 的情况下，改造道路中分值最大的那条分值尽量小。

需要输出两个整数：改造的道路数量 $s$ 和改造道路中的最大分值 $\max$。

---

关键观察

1. 问题本质

本题本质上是求图的最小生成树（Minimum Spanning Tree），更具体地说，是最小瓶颈生成树问题。

• 要求 1 和 2 意味着需要选择 $n-1$ 条边使图连通 → 形成一棵生成树。
• 要求 3 意味着在所有生成树中，选择最大边权最小的那棵 → 最小瓶颈生成树。

2. 重要性质

对于连通图，最小生成树一定是最小瓶颈生成树。因此，我们只需要求原图的最小生成树，那么：

• 改造的道路数量 = $n-1$
• 改造道路中的最大分值 = 最小生成树中的最大边权

---

算法设计

1. 最小生成树算法选择

由于 $n \le 300$，数据规模较小，可以使用 Prim 算法（邻接矩阵实现）或 Kruskal 算法。

本题给出的代码采用 Prim 算法，主要步骤如下：

初始化

memset(minn, 0x7f, sizeof(minn));  // minn[i]表示点i到当前生成树的最小距离
minn[1] = 0;                       // 从点1开始构建生成树
memset(u, 1, sizeof(u));           // u[i]表示点i是否在生成树中

Prim 算法核心

for (int i = 1; i <= n; ++i) {
    int k = 0;
    
    // 找到不在生成树中且距离当前生成树最近的点k
    for (int j = 1; j <= n; j++)
        if (u[j] && (minn[j] < minn[k]))
            k = j;
    
    u[k] = 0;  // 将点k加入生成树
    
    // 更新其他点到生成树的距离
    for (int j = 1; j <= n; j++)
        if (u[j] && g[k][j] != 0 && g[k][j] < minn[j])
            minn[j] = g[k][j];
}

计算答案

for (int i = 1; i <= n; ++i) {
    if (minn[i] > mmax)
        mmax = minn[i];
}
printf("%d %d", n - 1, mmax);

2. 算法正确性证明

生成树边数

一个有 $n$ 个顶点的连通图，其生成树恰好有 $n-1$ 条边。

最小瓶颈性

Prim 算法（或 Kruskal 算法）生成的最小生成树具有最小瓶颈性质：

• 假设存在另一棵生成树 $T'$，其最大边权小于最小生成树 $T$ 的最大边权。
• 考虑 $T$ 中最大边权的那条边 $e$，将其从 $T$ 中删除，$T$ 被分成两个连通分量。
• 根据最小生成树的切性质（cut property），连接这两个连通分量的边中，$e$ 是权值最小的。
• 因此 $T'$ 中连接这两个连通分量的边权值不小于 $e$ 的权值，矛盾。

---

复杂度分析

时间复杂度

• Prim 算法（邻接矩阵）：$O(n^2)$
  • 外层循环 $n$ 次，每次寻找最近的点 $O(n)$，更新距离 $O(n)$
  • 总时间复杂度 $O(n^2)$

对于 $n \le 300$，$O(n^2) = O(90000)$，完全可行。

空间复杂度

• 邻接矩阵存储：$O(n^2)$
• 辅助数组：$O(n)$

对于 $n \le 300$，邻接矩阵需要约 $300^2 \times 4 \text{ bytes} \approx 360 \text{ KB}$，在限制范围内。

---

代码实现要点

1. 数据结构选择

int g[310][310];    // 邻接矩阵存储边权
int minn[310];      // 各点到当前生成树的最小距离
bool u[310];        // 标记是否已在生成树中
int mmax = -1;      // 记录最小生成树中的最大边权

2. 初始化细节

• minn 数组初始化为一个很大的值（0x7f）
• 从点 1 开始构建生成树，minn[1] = 0
• u 数组初始化为 true，表示所有点都不在生成树中

3. 特殊处理

• 当两点之间没有道路时，g[u][v] = 0
• 更新距离时需检查 g[k][j] != 0
• 注意 minn[0] 初始化为 0x7f，所以第一次找最小点时 k 会被正确更新

4. 答案计算

• 改造的道路数量固定为 $n-1$
• 改造道路的最大分值 = minn 数组中的最大值
  • 注意：minn[1] = 0，应从 2 开始统计，或直接统计所有值取最大

---

算法优化思考

1. 稀疏图优化

如果 $m$ 远小于 $n^2$，可以使用 Kruskal 算法（$O(m \log m)$）或 堆优化的 Prim 算法（$O(m \log n)$）。

2. 邻接表存储

对于稀疏图，可使用邻接表代替邻接矩阵，节省空间。

3. 本题数据特点

由于 $n \le 300$，且 $c \le 10000$，使用 Prim 算法（邻接矩阵）简单高效，代码简洁。

---

算法标签

• 图结构
• 贪心
• 最小生成树
• Prim 算法

---

总结

本题通过最小生成树模型，将复杂的城市道路改造问题转化为经典的图论问题。利用最小生成树的性质：

• 保证连通性的同时边数最少（$n-1$ 条）
• 最小生成树具有最小瓶颈性质，满足"最大分值尽量小"的要求