P2330

[SCOI2005] 繁忙的都市

题目描述

城市 C 是一个非常繁忙的大都市，城市中的道路十分的拥挤，于是市长决定对其中的道路进行改造。城市 C 的道路是这样分布的：城市中有 $n$ 个交叉路口，有些交叉路口之间有道路相连，两个交叉路口之间最多有一条道路相连接。这些道路是双向的，且把所有的交叉路口直接或间接的连接起来了。每条道路都有一个分值，分值越小表示这个道路越繁忙，越需要进行改造。但是市政府的资金有限，市长希望进行改造的道路越少越好，于是他提出下面的要求：

改造的那些道路能够把所有的交叉路口直接或间接的连通起来。
在满足要求 1 的情况下，改造的道路尽量少。
在满足要求 1、2 的情况下，改造的那些道路中分值最大的道路分值尽量小。

任务：作为市规划局的你，应当作出最佳的决策，选择哪些道路应当被修建。

输入格式

第一行有两个整数 $n,m$ 表示城市有 $n$ 个交叉路口， $m$ 条道路。

接下来 $m$ 行是对每条道路的描述， $u, v, c$ 表示交叉路口 $u$ 和 $v$ 之间有道路相连，分值为 $c$ 。

输出格式

两个整数 $s, \mathit{max}$ ，表示你选出了几条道路，分值最大的那条道路的分值是多少。

输入输出样例

输入样例 #1

输出样例 #1

3 6

说明/提示

数据范围及约定

对于全部数据，满足 $1\le n\le 300$ ， $1\le c\le 10^4$ ， $1 \le m \le 8000$ 。

题解

1 篇题解

登录后即可使用 Markdown 发布题解。

YuyiLv.6👑 站长管理员

P2330 [SCOI2005] 繁忙的都市题解 Author: Yuyi 题意分析题目的核心要求翻译过来就是三句话： 1. 保证图连通； 2. 在连通的情况下，选取的边数最少（显然就是 $N 1$ 条边，也就是一棵生成树）； 3. 在所有生成树中，使得边权最大的那条边的权值尽量小。这其实就是求图的瓶颈生成树（Bottleneck Spanni…

点击展开完整题解点击收起题解

2026年8月9日 22:33

P2330 [SCOI2005] 繁忙的都市题解

Author: Yuyi

题意分析

题目的核心要求翻译过来就是三句话：

保证图连通；
在连通的情况下，选取的边数最少（显然就是 $N-1$ 条边，也就是一棵生成树）；
在所有生成树中，使得边权最大的那条边的权值尽量小。

这其实就是求图的瓶颈生成树（Bottleneck Spanning Tree）。根据最小生成树（MST）的性质，图的最小生成树一定是一棵瓶颈生成树！所以我们只需要像往常一样求一遍最小生成树，然后记录下这个过程中加入生成树的最大边权即可。

正解推导过程

我们毫无悬念地掏出 Kruskal 算法：

排序：将所有的道路按分值（边权）从小到大排序。
贪心连接：从边权最小的边开始尝试，如果边的两个端点不在同一个连通块里（并查集维护），就说明这条边不会造成环，果断将其加入生成树中。
记录答案：因为我们是按边权从小到大加边的，所以最后加进去的那条使图彻底连通的边，它的权值一定是我们选出的所有边里的最大值。
题目明确说明图是连通的，所以我们连满 $N-1$ 条边直接 break，输出 N-1 以及维护的最大边权即可。

正解代码及分析

#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define eps 1e-9
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dep(i,a,b) for(int i=(a);i>=(b);i--)
#define lowbit(a) (a)&(-a)
using namespace std;
const int maxn = 8005; //根据最大边数8000调整
const int mo = 998244353;
const double pi = acos(-1.0);
template <typename T>
inline void read(T &X)
{
    X = 0;int w = 0; char ch = 0;
    while(!isdigit(ch)) {w |= ch == '-' ;ch = getchar();}
    while(isdigit(ch)) X = X * 10 + (ch^48),ch = getchar();
    if(w) X = -X;
}
int n,m;
struct Edge
{
    int u,v;
    ll w;
}e[maxn];
bool cmp(Edge A,Edge B)
{
    return A.w < B.w;
}
int fa[maxn];
int find(int x)
{
    if(x == fa[x]) return x;
    return fa[x] = find(fa[x]);
}
void solve()
{
    read(n),read(m);
    rep(i,1,m) read(e[i].u),read(e[i].v),read(e[i].w);
    rep(i,1,n) fa[i] = i;
    sort(e+1,e+1+m,cmp);
    int cnt = 0;
    ll ans = 0;
    rep(i,1,m)
    {
        int fu = find(e[i].u);
        int fv = find(e[i].v);
        if(fu != fv)
        {
            fa[fu] = fv;
            ans = max(ans,e[i].w);
            cnt++;
        }
        if(cnt == n-1) break;
    }
    cout << cnt << " " << ans << endl;
    return;
}
int main()
{
    int T=1;
//  freopen("mul.in","r",stdin);
//  freopen("mul.out","w",stdout);
//  read(T);
    while(T--) solve();
    return 0;
}

复杂度分析

时间复杂度：本题点数 $N \le 300$ ，边数 $M \le 8000$ 。排序所需时间为 $O(M \log M)$ ，并查集的查询和合并时间复杂度接近 $O(1)$ 。因此总体时间复杂度为 $O(M \log M)$ ，对于这道题的数据范围简直就是降维打击，瞬间通过。
空间复杂度：需要存储 $M$ 条边以及并查集数组，通过统一大小的 maxn = 8005 开辟，空间复杂度稳定在 $O(M)$ ，极度安全。

讨论

0 条讨论

登录后即可使用 Markdown 发起讨论和回复。

还没有讨论，来发起第一条吧。