繁忙的都市(city)（信息学奥赛一本通- P1392）

【题目描述】

【输入】

【输出】

【输入样例】

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

【输出样例】

3 6

1. 算法分析

这道题看似需要一种特殊的“瓶颈”算法，但实际上，最小生成树 (MST) 本身就满足这个性质。

• MST 的定义是总权值和最小。

• 推论：MST同时也满足树中最大边权最小。

因此，我们只需要跑一遍标准的MST算法（Kruskal或Prim），然后找出树中权值最大的那条边即可。

2. 解法一：Kruskal 算法 (推荐)

核心思路：

Kruskal 算法将所有边按权值从小到大排序。

当我们贪心地选取边加入集合时，最后加入的那条边（第N-1条边），一定是当前生成树中权值最大的边。

代码亮点：

直接输出 mst[cnt].w，无需再次遍历寻找最大值。

//kruskal 核心：排序后，最后加入生成树的边，即为最大权值边。 #include <iostream> #include <algorithm>//sort using namespace std; int n,m; struct edge{ int u,v,w; //重载运算符，按边权从小到大排序 friend bool operator <(edge a,edge b){ return a.w<b.w; } }e[10010];//边集数组 edge mst[10010];//存最小生成树有多少条边 int cnt;//最小生成树边数 long long sum;//最小生成树的长度 int fa[310];//记录每个节点所在集合中的老大 //并查集查询+路径压缩 int find(int x){ if(fa[x]==x) return x;//如果是根节点就返回 //不是就递归找根节点，并把根节点赋给沿途所有节点 return fa[x]=find(fa[x]); } //合并 void uni(int a,int b){ int faa=find(a); int fab=find(b); if(faa!=fab){ fa[fab]=faa; } } void kruskal(){ for(int i=1;i<=m;i++){ int a=e[i].u;//边集数组第i条边一个端点 int b=e[i].v;//边集数组第i条边另外一个端点 if(find(a)!=find(b)){//如果两个端点不在一个集合就链接他们 cnt++; mst[cnt].u=a; mst[cnt].v=b; mst[cnt].w=e[i].w; sum+=e[i].w; uni(a,b); } } } int main(){ cin>>n>>m; //初始化边集数组自成集合，每个点是自己的老大 for(int i=1;i<=n;i++) fa[i]=i; for(int i=1;i<=m;i++){ cin>>e[i].u>>e[i].v>>e[i].w; } //对边集数组按边权从小到大排序 sort(e+1,e+m+1); kruskal(); cout<<cnt<<" "<<mst[cnt].w; }

3. 解法二：堆优化Prim算法

核心思路：

Prim算法通过优先队列每次选择离集合最近的点。

我们需要一个变量ma来记录入队并被选中的边的最大值。

每当一个点被正式加入集合（vis[nid]=1）时，更新 ma=max(ma, dis[nid])。

代码技巧：

cnt 初始化为 -1。因为起点加入集合时不算边，这样当跑完所有点后，cnt 刚好是N-1。

//prim+堆优化 #include <iostream> #include <cstring>//对应memset #include <algorithm>//对应max函数 #include <queue> using namespace std; int n,m; int h[310];//邻接表头指针数组 int vtex[20010];//第i条边的终点下表 int nxt[20010];//与第i条边同起点的下一条边的索引 int wt[20010];//第i条边的边权 int idx; int vis[310];//标记每个点是否已经连通（加入集合） int dis[310];//记录每个点到集合的距离 int cnt=-1;//记录连接上的边数 cnt初始化为-1，就是因为第一个点加入集合不需要边 int ma=0;//记录分值最大的那条道路的分值 long long sum;//最小生成树的总长度 struct node{ int id;//节点编号 int w;//节点权值 //优先队列默认最大堆，重载运算符改为最小堆 离集合最近的点优先出队 friend bool operator<(node a,node b){ return a.w>b.w; } }; priority_queue<node> q; void prim(int s){ dis[s]=0;//起点到自己距离为0 node tmp; tmp.id=s; tmp.w=0; q.push(tmp);//起点入队 while(!q.empty()){ tmp=q.top();//访问队首元素 q.pop();//队首出队 int nid=tmp.id; //如果tmp已经加入集合（出队过）就跳过 if(vis[nid]==1) continue; vis[nid]=1;//否则就链接上 cnt++;//cnt初始化为-1，就是因为第一个点加入集合不需要边 sum+=dis[nid]; ma=max(ma,dis[nid]); int p=h[nid]; while(p!=-1){//遍历tmp的所有邻接点 //如果该临接点尚未加入集合 且目前到集合距离大于经tmp到集合距离 就更新到集合距离 //为经tmp到集合距离 if(vis[vtex[p]]==0 && dis[vtex[p]]>wt[p]){ dis[vtex[p]]=wt[p]; q.push({vtex[p],wt[p]});//然后把这个点入队 } p=nxt[p];//更新指针 } } } void addedge(int u,int v,int w){ vtex[idx]=v; wt[idx]=w; nxt[idx]=h[u]; h[u]=idx++; } int main(){ cin>>n>>m; memset(h,-1,sizeof(h));//初始化头指针数组为空 memset(dis,0x3f,sizeof(dis));//初始化每个点到集合距离为无穷 //邻接表存图 for(int i=1;i<=m;i++){ int u,v,w; cin>>u>>v>>w; addedge(u,v,w);//双向边 addedge(v,u,w); } prim(1);// cout<<cnt<<" "<<ma; return 0; }

4. 总结

这两份代码都已通过测试，是标准的算法模板。对于“瓶颈生成树”类问题，Kruskal 通常更简单直观，因为它天然基于边权排序。