A28834. 繁忙的都市(city)
题目描述
繁忙的都市(city)
题目描述
城市C是一个非常繁忙的大都市，城市中的道路十分的拥挤，于是市长决定对其中的道路进行改造。城市C的道路是这样分布的：城市中有n个交叉路口，有些交叉路口之间有道路相连，两个交叉路口之间最多有一条道路相连接。这些道路是双向的，且把所有的交叉路口直接或间接的连接起来了。每条道路都有一个分值，分值越小表示这个道路越繁忙，越需要进行改造。但是市政府的资金有限，市长希望进行改造的道路越少越好，于是他提出下面的要求：
1．改造的那些道路能够把所有的交叉路口直接或间接的连通起来。
2．在满足要求1的情况下，改造的道路尽量少。
3．在满足要求1、2的情况下，改造的那些道路中分值最大值尽量小。
作为市规划局的你，应当作出最佳的决策，选择那些道路应当被修建。
输入
第一行有两个整数n,m表示城市有n个交叉路口，m条道路。接下来m行是对每条道路的描述，u, v, c表示交叉路口u和v之间有道路相连，分值为c。(1≤n≤300，1≤c≤10000)。
输出
两个整数s, max，表示你选出了几条道路，分值最大的那条道路的分值是多少。
输入样例
4 5
1 2 3
1 4 5
2 4 7
2 3 6
3 4 8输出样例
3 6参考答案
#include<bits/stdc++.h>
using namespace std;
#define N 305
struct Edge
{
int v, w;
Edge(){}
Edge(int a, int b):v(a),w(b){};
};
vector<Edge> edge[N];
bool vis[N];
int n, m, mx, dis[N];
void prim()
{
memset(dis, 0x3f, sizeof(dis));
dis[1] = 0;
for(int k = 1; k <= n; ++k)
{
int u = 0;
for(int i = 1; i <= n; ++i)
if(vis[i] == false && (u == 0 || dis[i] < dis[u]))
u = i;
vis[u] = true;
mx = max(mx, dis[u]);
for(Edge e : edge[u])
{
int v = e.v, w = e.w;
if(vis[v] == false && dis[v] > w)
dis[v] = w;
}
}
}
int main()
{
int f, t, w;
cin >> n >> m;
for(int i = 1; i <= m; ++i)
{
cin >> f >> t >> w;
edge[f].push_back(Edge(t, w));
edge[t].push_back(Edge(f, w));
}
prim();
cout << n-1 << ' ' << mx;
return 0;
}答案解析
将题目叙述转为图论概念，交叉路口为顶点，道路为边，道路是双向的，且所有交叉路口都直接或间接连接起来，说明这是无向连通图。每条道路的分值，就是边的权值。政府要改造一些道路，就是选一些边。
三个要求的概念分别为：
选择的边构成的图应该是连通图，且应该包含原图所有顶点。
选择的边尽可能少。
边最少时，该图就成了无根树。边数为顶点数减1。
综合以上两点，选择的边及顶点构成的图就是原图的生成树。
生成树有多种方案，选择其中权值最大的边最小的那一种生成树方案，即瓶颈生成树。
树上最大边权值在图的所有生成树中最小的生成树，叫做瓶颈生成树。
最小生成树一定是瓶颈生成树，但瓶颈生成树未必是最小生成树。（其证明见百度百科）
题目要求的就是瓶颈生成树，我们可以直接求出最小生成树，它一定是瓶颈生成树。
该题顶点数<=300，边数<=100000，使用Prim，Prim堆优化，Kruskal都可以完成该题。