关于最小生成树

2022/5/4 23:44:29

编程Tag： node return 生成 int find FA 最小 double 关于

本文主要是介绍关于最小生成树，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

1.定义：

一个有n个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有n个结点，并且有保持图连通的最少的边。

2.实现：

一般是用并查集的合并与查找操作来支撑的，这里简单提一下
先定义一个数组\(fa_i\)表示\(i\)的父节点

inline int find(int x)
{
	if(x==fa[x])
		return x;
	return fa[x]=find(fa[x]);
}//查找祖先 

inline void merge(int x,int y)
{
	int a=find(x);
	int b=find(y);
	if(a!=b)
	{
		fa[a]=b;
	}
}//合并x，y所在的集合

3.思路：

就是将边权从小到大排序然后依次查询看是否组成一颗生成树，若是则停止操作

温馨提示：

并查集一定要记得初始化！！！
并查集一定要记得初始化！！！
并查集一定要记得初始化！！！

典型例题：

例一 P3366 【模板】最小生成树

板子题......

Code

#include <bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;

struct node
{
	int u,v,w;
}e[MAXN];

int fa[MAXN]; 

int find(int x)
{
	if(x==fa[x])
		return x;
	return fa[x]=find(fa[x]);
}

inline void merge(int x,int y)
{
	int a=find(x);
	int b=find(y);
	if(a!=b)
	{
		fa[a]=b;
	}
}

inline bool cmp(node x,node y)
{
	return x.w<y.w;
}

int n,m;
int ans;
int cnt;
int main()
{
	scanf("%d%d",&n,&m);
	for(register int i=1;i<=n;i++)
	{
		fa[i]=i;	
	} 
	for(register int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
	}
	sort(e+1,e+m+1,cmp);
	for(register int i=1;i<=m;i++)
	{
		int x=find(e[i].u);
		int y=find(e[i].v);
		if(x!=y)
		{
			merge(x,y);
			ans+=e[i].w;
			cnt++;
		}
	}
	if(cnt!=n-1)
	{
		printf("orz");
	}
	else
	{
		printf("%d",ans);
	}
	return 0;
}

例二 P1991 无线通讯网

同样是板子题......

Code

#include <bits/stdc++.h>
using namespace std;

struct edge
{
	int u,v; 
	double w;
}e[250000];

int s,p;

inline double dis(double x1,double y1,double x2,double y2)
{
	double k=pow((x1-x2),2)+pow((y1-y2),2);
	return sqrt(k);
}

double x[505],y[505];
int cnt;

bool cmp(edge x,edge y)
{
	return x.w<y.w;
}

int fa[505];

int find(int x)
{
	if(x==fa[x])
		return x;
	return fa[x]=find(fa[x]);
}

inline void merge(int x,int y)
{
	int a=find(x);
	int b=find(y);
	if(a!=b)
	{
		fa[a]=b;
	}
}

int main()
{
	scanf("%d%d",&s,&p);
	for(register int i=1;i<=p;i++)
	{
		scanf("%lf%lf",&x[i],&y[i]);
		fa[i]=i;  
	}
	for(register int i=1;i<=p;i++)
	{
		for(register int j=i+1;j<=p;j++)
		{
			e[++cnt].u=i;
			e[cnt].v=j;
			e[cnt].w=dis(x[i],y[i],x[j],y[j]);
		}
	}
	sort(e+1,e+cnt+1,cmp);
	int ss=0;
	if(ss>=p-s)
	{
		cout<<0;  
		return 0;  
	}
	for(register int i=1;i<=cnt;i++)
	{
		int a=find(e[i].u);
		int b=find(e[i].v);
		if(a!=b)
		{
			merge(a,b);
			ss++;
		}
		if(ss==p-s)
		{
			printf("%.2lf",e[i].w);
			return 0; 
		}
	}
	return 0;
}

例三 P2872 Building Roads S

全是裸的生成树真的好吗......

Code

#include <bits/stdc++.h>
using namespace std;
int n,m,f[5005],cnt,id;
double ans;
long long x[5005],y[5005];
inline int read()
{
	register int x=0,f=0;register char ch=getchar();
	while(ch<'0' || ch>'9')f|=ch=='-',ch=getchar();
	while(ch>='0' && ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return f?-x:x;
}
struct node{
	int x,y;
	long long w;
	bool operator<(const node &X)const{
		return w<X.w;
	}
}q[2000005];
int getf(int x){
	int y=x,z;
	while(x!=f[x])x=f[x];
	while(y!=x)z=y,y=f[y],f[z]=x;
	return x;
}
int main(){
	n=read();m=read();
	for(int i=1;i<=n;i++){
		f[i]=i;
	}
	for(int i=1;i<=n;i++){
		x[i]=read();y[i]=read();
	}
	for(int i=1;i<=m;i++){
		int u,v;
		u=read();v=read();
		int fx=getf(u),fy=getf(v);
		if(fx==fy)continue;
		f[fx]=fy;
		cnt++;
	}
	if(cnt==n-1){
		puts("0.00");
		return 0;
	}
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			id++;
			q[id].x=i,q[id].y=j;
			q[id].w=1ll*(x[i]-x[j])*(x[i]-x[j])+1ll*(y[i]-y[j])*(y[i]-y[j]);	
		}
	}
	sort(q+1,q+1+id);
	for(int i=1;i<=id;i++){
		int fx=getf(q[i].x),fy=getf(q[i].y);
		if(fx==fy)continue;
		f[fx]=fy;
		ans+=sqrt(q[i].w);
		cnt++;
		if(cnt==n-1){
			printf("%.2lf",ans);
			break;
		}
	}
	return 0;
}

例四 P1195 口袋的天空

又是板子题？？！！

Code

#include <bits/stdc++.h>
using namespace std;
int n,k,m;
int fa[1000050];
struct node {
	int x;
	int y;
	int l;
} a[1000005];
int cmp( const void *a , const void *b ) {
	struct node *c = (node *)a;
	struct node *d = (node *)b;
	return c->l - d->l;
}
int find(int x)
{
	if(x!=fa[x])
	fa[x]=find(fa[x]);
	return fa[x];
}
void work(int x,int y)
{
	x=find(x);
	y=find(y);
	if(x==y)
	return;
	fa[x]=y;
}
int main() {
	cin>>n>>m>>k;
	for(int i=0; i<m; i++) {
		scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].l);
	}
	qsort(a,m,sizeof(a[0]),cmp);
	for(int i=1;i<=n;i++)
	fa[i]=i;
	int num=n-k;
	int ans=0;
	for(int i=0;i<m;i++)
	{
		if(num==0)
		break;
		int aaa=find(a[i].x);
		int wzx=find(a[i].y);
		if(aaa!=wzx)
		{
			work(a[i].x,a[i].y);
			ans+=a[i].l;
			num--;
		}
	}
	if(num)
	cout<<"No Answer"<<endl;
	else
	cout<<ans<<endl;
}

例五 P1547 Out of Hay S

真的不要再来裸题了......

#include <bits/stdc++.h>
using namespace std;
int n,m;
long long fa[100000001];
struct hay
{
	int x,y,z;
}a[10001];
inline bool cmp(hay a,hay b)
{
	return a.z<b.z;
}
inline int find(int t)
{
	if(fa[t]==t) return t;
    else return fa[t]=find(fa[t]);
} 
inline void me(int r1,int r2)
{
	int s1=find(r1);
	int s2=find(r2);
	fa[s1]=s2;	
}
inline void Kruskal()
{
	int k=0;
	int k1,k2;
	int ans=0;
	for(int i=1;i<=m;i++)
	{
		k1=find(a[i].x);
		k2=find(a[i].y);
		if(k1==k2) continue;
		k++;
		me(k1,k2);
	
		ans=max(a[i].z,ans);
		if(k==n-1) break;
	}
	cout<<ans;
}
int main()
{
	cin>>n>>m;
	int i;
	for(i=1;i<=n;i++)
	{
		fa[i]=i;
	}
	for(i=1;i<=m;i++)
	{
		cin>>a[i].x>>a[i].y>>a[i].z;
	} 
	sort(a+1,a+m+1,cmp);
	Kruskal();
	return 0;
}

例六 P1396营救

终于不是裸题了，这道题还是需要一些特殊处理的，首先题目要读懂，理解对，其次是需要做些特殊处理

Code

#include <bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;

struct node
{
	int u,v,w;
}e[MAXN];

int fa[MAXN]; 

int find(int x)
{
	if(x==fa[x])
		return x;
	return fa[x]=find(fa[x]);
}

inline void merge(int x,int y)
{
	int a=find(x);
	int b=find(y);
	if(a!=b)
	{
		fa[a]=b;
	}
}

bool cmp(node x,node y)
{
	return x.w<y.w;
}

int n,m,s,t;
int ans=-1;
int main()
{
	scanf("%d%d%d%d",&n,&m,&s,&t);
	for(register int i=1;i<=n;i++)
	{
		fa[i]=i;
	} 
	for(register int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
	}
	sort(e+1,e+m+1,cmp);
	for(register int i=1;i<=m;i++)
	{
		int x=find(e[i].u);
		int y=find(e[i].v);
		if(x!=y)
		{
			merge(x,y);
			if(find(s)==find(t))
			{
				cout<<e[i].w;  
				return 0; 
			}
		}
	}
	return 0;
}

例七 P2330 繁忙的都市

这道题其实就是克鲁斯卡尔算法（Kruskal）的模板题，很简单。

Code

#include <bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;

struct node
{
	int u,v,w;
}e[MAXN];

int fa[MAXN]; 

int find(int x)
{
	if(x==fa[x])
		return x;
	return fa[x]=find(fa[x]);
}

inline void merge(int x,int y)
{
	int a=find(x);
	int b=find(y);
	if(a!=b)
	{
		fa[a]=b;
	}
}

bool cmp(node x,node y)
{
	return x.w<y.w;
}

int n,m,s,t;
int ans=-1;
int main()
{
	scanf("%d%d",&n,&m);
	for(register int i=1;i<=n;i++)
	{
		fa[i]=i;	
	} 
	for(register int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
	}
	sort(e+1,e+m+1,cmp);
	int k=0;
	for(register int i=1;i<=m;i++)
	{
		int x=find(e[i].u);
		int y=find(e[i].v);
		if(x!=y)
		{
			ans=e[i].w;
			merge(e[i].u,e[i].v);
			k++;
			if(k==n-1)
				break;
		}
	}
	printf("%d %d",n-1,ans);
	return 0;
}


这篇关于关于最小生成树的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！


相关编程文章

更多>
本站官方QQ
官方QQ:
23002807

沪ICP备2023033072号-1

     

扫一扫关注最新编程教程