题目描述
有一张城市地图,图中的顶点为城市,编号为 1∼n,无向边 代表两个城市间的连通关系,边上的权值为在这两个城市之间修建高速公路的造价,研究后发现,这个地图有一个特点,即任何一对城市都是连通的。
现在的问题是,要修建若干高速公路把所有城市联系起来,问如何设计可使得工程的总造价最少?
输入格式
第一行包含两个整数 n 和 e,分别表示城市个数和无向边个数。
接下来 e 行,每行包含三个整数 i,j,w,表示在城市 i 和城市 j 之间修建公路的造价为 w。
城市编号从 1 开始。
输出格式
共 n−1 行,每行为两个城市的编号,表明在这两个城市间建一条高速公路。
本题答案不一定唯一,输出任意一种最优方案即可,方案中边和点的顺序可以任意选择。
数据范围
1≤n≤100,
1≤e≤1000,
1≤w≤10000
数据保证不含重边和自环。
样例
输入样例:
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
朴素Prim算法
时间复杂度 $O(n^2 + e)$
C++ 代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
const int N = 105, INF = 0x3f3f3f3f;
int dist[N];
int g[N][N];
bool st[N];
int n, e;
void Prim(){
for(int i = 1; i <= n; i++) dist[i] = g[1][i];
dist[1] = 0;
st[1] = true;
while(true){
int v = -1, mind = 1e9;
for(int i = 1; i <= n; i++){
if(!st[i] && dist[i] < mind){
mind = dist[i];
v = i;
}
}
if(v == -1) break;
//需要在已收录的点中找到对应的边
for(int i = 1; i <= n; i++){
if(st[i] && mind == g[v][i]){
printf("%d %d\n", i, v);
break;
}
}
st[v] = true;
for(int i = 1; i <= n; i++){
if(!st[i] && g[v][i] != INF && dist[i] > g[v][i])
dist[i] = g[v][i];
}
}
}
int main(void){
scanf("%d %d", &n, &e);
int a, b, c;
memset(g, 0x3f, sizeof(g));
for(int i = 0; i < e; i++){
scanf("%d %d %d", &a, &b, &c);
g[a][b] = g[b][a] = c;
}
Prim();
return 0;
}
Kruskal算法
时间复杂度 $O(eloge)$
C++ 代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
const int N = 1010;
typedef struct{
int u;
int v;
int w;
} Edge;
Edge E[N]; //存边
int S[N]; //并查集
int n, e;
//路径压缩
int find(int x){
if(S[x] < 0) return x;
return S[x] = find(S[x]);
}
//按秩归并
void Union(int root1, int root2){
if(S[root1] < S[root2])
S[root2] = root1;
else if(S[root1] == S[root2]){
S[root1]--;
S[root2] = root1;
}
else{
S[root1] = root2;
}
}
//按边权从小到大排序
int cmp(const void *a, const void *b){
return ((Edge*)a)->w - ((Edge*)b)->w;
}
void Kruskal(){
memset(S, -1, sizeof(S));
qsort(E, e, sizeof(Edge), cmp);
int cnt = 0, idx = 0;
while(cnt != n - 1){ //共需要添加n-1条边
int x1 = E[idx].u, x2 = E[idx].v;
int root1 = find(x1);
int root2 = find(x2);
if(root1 != root2){
Union(root1, root2);
printf("%d %d\n", x1, x2);
cnt++;
}
idx++;
}
}
int main(void){
scanf("%d %d", &n, &e);
int a, b, c;
for(int i = 0; i < e; i++){
scanf("%d %d %d", &a, &b, &c);
E[i].u = a, E[i].v = b, E[i].w = c;
}
Kruskal();
return 0;
}