yuzh的博客

❤ ECUST ❤

0%

最小生成树

发表于 更新于 Valine：

最小生成树

模板：P3366 【模板】最小生成树 - 洛谷

Prim算法

  1. 将任意节点作为根，并找出与之相邻的所有边，获取未获得答案的节点中dis最小的节点(dis用于记录节点到所有邻接点的最短距离)
  2. 标记获得的最小节点cur的访问状态为true
  3. 将cur节点的临界点dis值进行更新
  4. 以cur节点作为根继续搜索下一个dis最小的节点
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
// Prim
bool flag[maxn];
memset(flag, false, sizeof(flag));
bool pd=false;
int ans=0, dis[maxn];
dis[1]=0;
for(int i=2;i<=n;i++)
{
    dis[i]=0x7f7f7f;
}
for(int i=1;i<=n;i++)
{
    int temp=0x7f7f7f, cur, pnt;
    for(int j=1;j<=n;j++)
    {
        if(flag[j]==false && temp>dis[j])
        {
            temp=dis[j];
            cur=j;
            pnt=edge[j].to;
        }
    }
    if(temp==0x7f7f7f) pd=true;
    flag[cur]=true;

    for(int j=head[cur];j!=-1;j=edge[j].next)
    {
        if(!flag[edge[j].to] && dis[edge[j].to]>edge[j].weight)
        {
            dis[edge[j].to]=edge[j].weight;
        }
    }
    ans+=temp;
}

Kruskal算法

  1. 将边从小到大排序
  2. 若没有回路，则添加当前边
  3. 边数达到n-1时，最小生成树建成
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
bool cmp(Edge a, Edge b)
{
	return a.weight<b.weight;
}

int fa[maxn];
int findroot(int x) { return fa[x] == x ? x : fa[x] = findroot(fa[x]); }
void Merge(int x, int y) {
	x = findroot(x);
	y = findroot(y);
	fa[x] = y;
}

int main()
{
	int n,m;
	cin>>n>>m;
	
	for(int i=1;i<=n;i++){ fa[i]=i; }
	for(int i=1,u,v,w;i<=m;i++)
	{
		cin>>u>>v>>w;
		addEdge(u,v,w);
		addEdge(v,u,w);
	}
	sort(edge, edge+m*2, cmp);
	int ans=0;
	for(int i=0;i<m*2;i++)
	{
		if(findroot(edge[i].from)!=findroot(edge[i].to))
		{
			Merge(edge[i].from,edge[i].to);
			ans+=edge[i].weight;
		}
	}
	cout<<ans;
	return 0;
}