文章

5

粉丝

409

获赞

7

访问

52.6k

头像
Kruscal模板24ms
P1611 中山大学机试题
发布于2020年5月1日 12:54
阅读数 8.2k

Kruscal是采用贪心思想,基于加边策略的MST算法。

用并查集管理顶点之间的连通性。

操作两步走:

1.对所有边按照权重升序进行排序

2.从权重最小的边开始,遍历所有的边,只要两个顶点没有连通,则添加这条边,同时统计权重

#include<cstdio>
#include<vector>
#include<algorithm> 
using namespace std;
#define N 5005 //点 
#define M 200005 //边 
struct Edge{
	int s;//起点 
	int e;//终点 
	int w;//权重
	
	Edge(int si,int ei,int wi)
	{
		s=si;e=ei;w=wi;
	}
	
	bool operator< (const Edge& b) const{
		return w<b.w;
	}
};

struct Union{

	int par[N];
	int count;//集合个数 
	Union(int n)
	{
		for(int i=0;i<n;i++)
			par[i]=-1;
		count = n; 
	}
	
	bool unite(int a,int b)
	{
		int ra = find(a);
		int rb = find(b);
		if(ra!=rb)
		{
			par[ra]=rb;
			count--;
			return true;
		}
		return false;
			
		
	}
	
	int find(int x)
	{
		if(par[x]==-1) return x;
		else{
			int root = find(par[x]);
			par[x] = root;//路径压缩
			return root;
		}
	}
};

vector<Edge> edges;

int main()
{
	
	//读入边
	int n,m;

	scanf("%...
登录查看完整内容


登录后发布评论

1 条评论
admin SVIP
2020年5月1日 19:47

赞一个,kruskalwink

赞(1)