Ink on paper(最小生成树

（Kruskal）mlogm

#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define ll long long
const int N=5e3+10;
int fa[N],tot=0,Tot=0;
int find(int x){
    if(fa[x]==x) return  x;
    else return fa[x]=find(fa[x]);
}
void Union(int x,int y){
    int fx=find(x),fy=find(y);
    if(fx!=fy) fa[fy]=fx,Tot++;
}
int T,n;ll x[N],y[N];
struct node{
     int x,y;ll dis;
    bool operator <(const node &b)const
    {
        return dis<b.dis;
    }
}Node[N*N];
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);tot=0;
        for(int i=1;i<=n;i++) scanf("%lld%lld",&x[i],&y[i]);
        for(int i=1;i<=n;i++){
            for(int j=i+1;j<=n;j++) Node[++tot]={i,j,(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])};
        }
        for(int i=0;i<=n;i++) fa[i]=i;
        sort(Node+1,Node+tot+1);
        Tot=0;
        for(int i=1;i<=tot;i++){
            Union(Node[i].x,Node[i].y);
            if(Tot==n-1) {printf("%lldn",Node[i].dis);break;}
        }
    }
}

prim nlogn+m

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll INF=0x3f3f3f3f3f3f3f3f;
ll e[5500][5500],dis[5500],x[5500],y[5500];
int book[5500],n;
void init(){
	for(int i=1;i<=n;i++)    e[i][i]=0;
}
ll dist(int i,int j){
	return (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
}
void Prim()
{
	int i,j,u,v;
	memset(book,0,sizeof(book));
	for(i=1;i<=n;i++)   dis[i]=e[1][i];
	book[1]=1;            //把1加入到树中
	ll mind,ans=0;
	for(i=1;i<=n-1;i++)
	{
    	mind=INF;u=-1;
    	for(j=1;j<=n;j++)
    	{
        	if(!book[j]&&mind>dis[j])
        	{
            	mind=dis[j];
            	u=j;
        	}
    	}
    	if(u==-1)    break;
    	ans=max(ans,dis[u]);
    	book[u]=1;
    	for(v=1;v<=n;v++)
    	{
        	if(!book[v]||e[u][v]<INF)
        	{
            	if(dis[v]>e[u][v])
                	dis[v]=e[u][v];
        	}
    	}
	}
	printf("%lldn",ans);
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
    	scanf("%d",&n);
    	for(int i=1;i<=n;i++)    
        	scanf("%lld %lld",&x[i],&y[i]);
    	init();
    	for(int i=1;i<=n;i++)
        	for(int j=i+1;j<=n;j++)
            	e[i][j]=e[j][i]=dist(i,j);
    	Prim();
	}
	return 0;
}

最后

以上就是陶醉仙人掌为你收集整理的Ink on paper(最小生成树的全部内容，希望文章能够帮你解决Ink on paper(最小生成树所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。