题目描述
给定一个n个点m条边的无向图,图中可能存在重边和自环,边权可能为负数。
求最小生成树的树边权重之和,如果最小生成树不存在则输出impossible。
给定一张边带权的无向图G=(V, E),其中V表示图中点的集合,E表示图中边的集合,n=|V|,m=|E|。
由V中的全部n个顶点和E中n-1条边构成的无向连通子图被称为G的一棵生成树,其中边的权值之和最小的生成树被称为无向图G的最小生成树。
输入格式
第一行包含两个整数n和m。
接下来m行,每行包含三个整数u,v,w,表示点u和点v之间存在一条权值为w的边。
输出格式
共一行,若存在最小生成树,则输出一个整数,表示最小生成树的树边权重之和,如果最小生成树不存在则输出impossible。
数据范围
1≤n≤500,
1≤m≤105,
图中涉及边的边权的绝对值均不超过10000。
输入样例:
4 5
1 2 1
1 3 2
1 4 3
2 3 2
3 4 4
输出样例:
6
思路
1.最小生成树在许多领域都有重要的作用,例如
要在 n 个城市之间铺设光缆,使它们都可以通信
铺设光缆的费用很高,且各个城市之间因为距离不同等因素,铺设光缆的费用也不同
如何使铺设光缆的总费用最低?
2.如果图的每一条边的权值都互不相同,那么最小生成树将只有一个,否则可能会有多个最小生成树
3.求最小生成树的2个经典算法
Prim(普里姆算法) O(n^2)
Kruskal(克鲁斯克尔算法)O(mlogm)//基于对边的判断,因为是生成树,在合成树结构的过程中,不能有环,采并集解决问题,后面再讲
4.Prim算法是基于切分定理
4.1.切分(Cut):把图中的节点分为两部分,称为一个切分
4.2.下图有个切分 C = (S, T),S = {A, B, D},T = {C, E}
4.3.横切边(Crossing Edge):如果一个边的两个顶点,分别属于切分的两部分,这个边称为横切边
比如上图的边 BC、BE、DE 就是横切边
4.4.切分定理:给定任意切分,横切边中权值最小的边必然属于最小生成树
5.实例
t = A
st[A] = true;
dist = [A->B 4, A->H 8] (保存有意义的)
t = B
st[B] = true;
切边 dist = [A->H 8 B->C 8 , B->H 11] //A->B 4抛弃,因为在集合中了,在找t的过程中不会参与最短权边的查找
t = C
st[C] = true;
切边 dist = [A->H 8, B->H 11, C->I 2, C->D 7 C->F 4]
t = I
st[I] = true;
切边 dist = [A->H 8, B->H 11, C->D 7 C->F 4, I->H 7 I->G 6]
t = F
st[F] = true;
切边 dist = [A->H 8, B->H 11, C->D 7, I->H 7 I->G 6, F->D 14, F->E 10 F->G 2]
t = G
st[G] = true;
切边 dist = [A->H 8, B->H 11, C->D 7, I->H 7, F->D 14, F->E 10 G->H 1]
t = H
st[H] = true;
切边 dist = [ C->D 7, F->D 14, F->E 10]
t = D
st[D] = true;
切边 dist = [F->E 10, D->E 9]
t = E
st[E] = true;
切边 dist = []
结束结果
java
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static int N = 510, INF = 0x3f3f3f3f;
static int n, m;
static int [][] g = new int[N][N];
static int [] dist = new int[N];
static boolean[] st = new boolean[N];
private static int prime() {
Arrays.fill(dist, INF);
int res = 0;
for (int i = 0; i < n; i ++) {
int t = -1;
for (int j = 1; j <= n; j ++) {
if (!st[j] && (t == -1 || dist[t] > dist[j])) {
t = j;
}
}
if (i != 0 && dist[t] == INF) return INF;
if (i != 0) {
res += dist[t];
}
for (int j = 1; j <= n; j ++) {
dist[j] = Math.min(dist[j], g[t][j]);
}
st[t] = true;
}
return res;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
for (int i = 0; i < N; i++) {
Arrays.fill(g[i], INF);
}
while (m -- > 0) {
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
g[a][b] = g[b][a] = Math.min(g[a][b], c);
}
int t = prime();
if (t == INF) System.out.println("impossible");
else System.out.println(t);
}
}
c++
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 510, INF = 0x3f3f3f3f;
int n, m;
int g[N][N];
int dist[N];
bool st[N]; //记录当前点在集合内还是集合外
int prim(){
memset(dist, 0x3f, sizeof dist);
int res = 0;
for(int i = 0; i < n; i++){ //要遍历n个点
//找一个最短边权的点
int t = -1; //初始化为没有找到的点
for(int j = 1; j <= n; j ++){
if(!st[j] && (t == -1 || dist[t] > dist[j])){
t = j;
}
}
//不是第一个取出的节点,并且当前节点的距离为INF,则表示没有和集合中点相连的边。
if(i && dist[t] == INF) return INF;
//不是第一个取出的节点,是其他点与集合中的连接线(最小边)
//写在前面,如果一个节点本身出现负环,下面这句更新后,会影响结果,比如g[t][j],当t = j,更新了g[t][t],影响res结果
//比如4->4 -10, 更新后dist[4] = min(dist[4], g[4][4])
if(i) res += dist[t];
//更新当前最短边权点t到集合的距离(保留最小的值,如果比之前最短t到集合的距离还小,更新)
for(int j = 1; j <= n; j ++) dist[j] = min(dist[j], g[t][j]);
st[t] = true;
}
return res;
}
int main(){
scanf("%d%d", &n, &m);
memset(g, 0x3f, sizeof g);
while(m --){
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
g[a][b] = g[b][a] = min(g[a][b], c);
}
int t = prim();
if(t == INF) puts("impossible"); //有点不连通的时候,不存在最小生成树
else printf("%d", t);
return 0;
}
tql
非常棒
if(i && dist[t] == INF) 这个i&&有什么作用
特判第一个加入集合的点,第一个加入集合的点dist[t] = INF,若没有i &&则会返回INF。
tqltql感谢大佬!!!
很棒哈哈哈~
哈哈哈哈哈哈哈哈哈哈哈啊哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈啊哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈啊哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈1哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈
牛