A28831. 城市公交网建设问题
填空题
困难
知识点
题目描述
城市公交网建设问题
题目描述
有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权为在这两个城市之间修建高速公路的造价，研究后发现，这个地图有一个特点，即任一对城市都是连通的。现在的问题是，要修建若干高速公路把所有城市联系起来，问如何设计可使得工程的总造价最少？
输入
n（城市数，1<≤n≤100）
e（边数）
以下e行，每行3个数 i,j,wij，表示在城市i,j之间修建高速公路的造价。
输出
n-1行，每行为两个城市的序号，表明这两个城市间建一条高速公路。
输入样例
5 8
1 2 2
2 5 9
5 4 7
4 1 10
1 3 12
4 3 6
5 3 3
2 3 8输出样例
1 2
2 3
3 4
3 5参考答案
#include<bits/stdc++.h>
using namespace std;
#define N 105
struct Edge
{
int v, w;
Edge(){}
Edge(int a, int b):v(a),w(b){}
};
int n, m, dis[N], from[N];//from[i]到顶点i的一条边是最小生成树中的边
bool vis[N];
vector<Edge> edge[N];
set<pair<int, int>> tree;//保存生成树的所有边
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;
if(from[u] != 0)
tree.insert(make_pair(min(from[u], u), max(from[u], u)));//from[u]和u的较小值为pair的first，较大值为second
for(Edge e : edge[u])
{
int v = e.v, w = e.w;
if(vis[v] == false && dis[v] > w)
{
dis[v] = w;
from[v] = u;
}
}
}
}
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();
for(pair<int, int> p : tree)
cout << p.first << " " << p.second << endl;
return 0;
}
上一题
下一题