GGAutomaton's Blog
0%

最小生成树Prim算法模板

发表于 分类于 ，

不带堆优化，时间复杂度\(\ O(V^2)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<iostream>
#include<cstdio>
#include<climits>
int head[105],vet[10005],w[10005],next[10005],num;
int dist[105];
bool f[105];
void addedge(int x,int y,int c) {
	num++;
	vet[num]=y;
	w[num]=c;
	next[num]=head[x];
	head[x]=num;
}
int main() {
	int n,m,ans=0;
	std::cin >> n >> m;
	for (int i=1;i<=m;i++) {
		int x,y,c;
		scanf("%d%d%d",&x,&y,&c);
		addedge(x,y,c);
		addedge(y,x,c);
	}
	for (int i=1;i<=n;i++) dist[i]=INT_MAX;
	dist[1]=0;
	for (int i=1;i<=n;i++) {
		int mindist=INT_MAX,p=0;
		for (int j=1;j<=n;j++)
			if (!f[j] && mindist>dist[j]) {
				mindist=dist[j];
				p=j;
			}
		f[p]=true;
		ans+=dist[p];
		for (int e=head[p];e!=0;e=next[e])
			if (!f[vet[e]])
				dist[vet[e]]=std::min(dist[vet[e]],w[e]);
	}
	std::cout << ans;
	return 0;
}

堆优化，时间复杂度\(\ O(ElogE)\)
priority_queue实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<iostream>
#include<cstdio>
#include<climits>
#include<queue>
struct node {
	int p,weight;
	bool operator<(const node &a)const {
		return weight>a.weight;
	}
};
int head[100005],vet[200005],w[200005],next[200005],num;
int dist[100000];
bool f[100005];
void addedge(int x,int y,int c) {
	num++;
	vet[num]=y;
	w[num]=c;
	next[num]=head[x];
	head[x]=num;
}
int main() {
	int n,m;
	int ans=0;
	std::cin >> n >> m;
	for (int i=1;i<=m;i++) {
		int x,y,c;
		scanf("%d%d%d",&x,&y,&c);
		addedge(x,y,c);
		addedge(y,x,c);
	}
	for (int i=1;i<=n;i++) dist[i]=INT_MAX;
	dist[1]=0;
	std::priority_queue<node> qu;
	node newnode;
	newnode.weight=0;
	newnode.p=1;
	while (!qu.empty()) qu.pop();
	qu.push(newnode);
	for (int i=1;i<=n;i++) {
		while (f[qu.top().p]) qu.pop();
		newnode=qu.top();
		qu.pop();
		f[newnode.p]=true;
		ans+=newnode.weight;
		for (int e=head[newnode.p];e!=0;e=next[e])
			if (!f[vet[e]] && dist[vet[e]]>w[e]) {
				newnode.p=vet[e];
				newnode.weight=w[e];
				dist[vet[e]]=w[e];
				qu.push(newnode);
			}
	}
	std::cout << ans;
	return 0;
}

反向映射堆：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include<iostream>
#include<cstdio>
#include<climits>
struct node {
    int p,weight;
    bool operator<(const node &a)const {
        return weight<a.weight;
    }
};
int head[100005],vet[200005],w[200005],next[200005],num;
int dist[100005],hsize,po[100005];
node heap[200005];
bool f[100005];
void addedge(int x,int y,int c) {
    num++;
    vet[num]=y;
    w[num]=c;
    next[num]=head[x];
    head[x]=num;
}
void sw(int p1,int p2) {
	po[heap[p1].p]=p2;
	po[heap[p2].p]=p1;
	node tmp=heap[p1];
	heap[p1]=heap[p2];
	heap[p2]=tmp;
}
void Up(int p) {
	while (p>1) {
		if (heap[p]<heap[p/2]) {
			sw(p,p/2);
			p/=2;
		}
		else break;
	}
}
void Down(int p) {
	while (p*2<=hsize) {
		int Min=p;
		if (heap[p*2]<heap[Min]) Min=p*2;
		if (p*2<hsize && heap[p*2+1]<heap[Min]) Min=p*2+1;
		if (Min != p) {
			sw(p,Min);
			p=Min;
		}
		else break;
	}
}
void decrease_key(int t,int v) {
	heap[t].weight=v;
	Up(t);
}
void heap_push(node res) {
	heap[++hsize]=res;
	po[res.p]=hsize;
	Up(hsize);
}
node heap_pop() {
	sw(1,hsize);
	hsize--;
	Down(1);
	po[heap[hsize+1].p]=0;
	return heap[hsize+1];
}
int main() {
    int n,m;
    int ans=0;
    std::cin >> n >> m;
    for (int i=1;i<=m;i++) {
        int x,y,c;
        scanf("%d%d%d",&x,&y,&c);
        addedge(x,y,c);
        addedge(y,x,c);
    }
    for (int i=1;i<=n;i++) dist[i]=INT_MAX;
    dist[1]=0;
    heap_push((node){1,0});
    for (int i=1;i<=n;i++) {
        node newnode=heap_pop();
        f[newnode.p]=true;
        ans+=newnode.weight;
        for (int e=head[newnode.p];e!=0;e=next[e])
            if (!f[vet[e]] && dist[vet[e]]>w[e]) {
            	if (po[vet[e]]==0) heap_push((node){vet[e],w[e]});
            	decrease_key(po[vet[e]],w[e]);
                dist[vet[e]]=w[e];
            }
    }
    std::cout << ans;
    return 0;
}