最小生成树 Prim和Kruskal

感觉挺简单的,Prim和Dijkstra差不多,Kruskal搞个并查集就行了,直接上代码吧,核心思路都是找最小的边.

Prim

int n,m;

int g[N][N];

int u,v;

int dis[N];

bool st[N];

int prim(){

	me(dis,INF,sizeof(dis));

	int res=0;

	for(int i=0;i<n;++i){

		int t=-1;

		for(int j=1;j<=n;++j){

			if(!st[j] && (t==-1 || dis[t]>dis[j])) t=j;

		}

		if(i && dis[t]==INF) return INF;

		if(i) res+=dis[t];

		for(int j=1;j<=n;++j){

			dis[j]=min(dis[j],g[t][j]);

		}

		st[t]=true;

	}

	return res;

}

int main() {

    scanf("%d %d",&n,&m);

    me(g,INF,sizeof(g));

    for(int i=1;i<=m;++i){

    	int a,b,c;

    	scanf("%d %d %d",&a,&b,&c);

    	g[a][b]=g[b][a]=min(g[a][b],c);

    }

    int t=prim();

    if(t==INF) puts("impossible");

    else printf("%d\n",t);

    return 0;

}

Kruskal

struct misaka{

	int a,b;

	int val;

}e[N];

int n,m;

int p[N];

bool cmp(misaka n,misaka m){

	return n.val<m.val;

}

int find(int x){

	if(p[x]!=x) p[x]=find(p[x]);

	return p[x];

}

int main() {

     scanf("%d %d",&n,&m);

     for(int i=0;i<m;++i){

     	int a,b,val;

     	scanf("%d %d %d",&a,&b,&val);

     	e[i]={a,b,val};

     }	

     sort(e,e+m,cmp);

     for(int i=1;i<=n;++i)   p[i]=i;

     int res=0;

     int cnt=0;

     for(int i=0;i<m;++i){

     	int a=e[i].a;

     	int b=e[i].b;

     	int val=e[i].val;

     	a=find(a);

     	b=find(b);

     	if(a!=b){

     		p[a]=b;

     		res+=val;

     		cnt++;

     	}

     }

     if(cnt<n-1) puts("impossible");

     else printf("%d\n",res);

    return 0;

}

巴特西

最小生成树 Prim和Kruskal

最新文章

热门文章