技术教程 编程教程 [ACM]TL-Kruskal 正文

[ACM]TL-Kruskal

2023-04-28,,

#include<iostream>

#include<cstdio>

using namespace std;

struct edge

{

	int u;

	int v;

	int w;

};

struct edge e[10];

int n,m;

int f[7]={0},sum=0,count=0;

void quicksort(int left,int right)

{

	int i,j;

	struct edge t;

	if(left>right)	return;

	i=left;

	j=right;

	while(i!=j)

	{

		while(e[j].w >= e[left].w && i<j)

			j--;

		while(e[i].w <= e[left].w && i<j)

			i++;

		if(i<j)

		{

			t=e[i];

			e[i]=e[j];

			e[j]=t;

		}

	}

	t=e[left];//->j

	e[left]=e[i];

	e[i]=t;

	quicksort(left, i-1);

	quicksort(i+1, right);

	return;

}

int getf(int v)

{

	if(f[v]==v)	return v;

	else

	{

		f[v]=getf(f[v]);

		return f[v];

	}

}

int merge(int y,int u)

{

	int t1,t2;

	t1=getf(y);

	t2=getf(u);

	if(t1!=t2)

	{

		f[t2]=t1;

		return 1;

	}

	return 0;

}

int main(){

	cin>>n>>m;

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

		cin>>e[i].u>>e[i].v>>e[i].w;

	quicksort(1, m);

	for(int i=1;i<=n;i++)

		f[i]=i;

	//Kruskal

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

	{

		if(merge(e[i].u, e[i].v))

		{

			count++;

			sum+=e[i].w;

		}

		if(count==n-1)

			break;

	}

	cout<<sum;

	return 0;

}

[ACM]TL-Kruskal的相关教程结束。

《[ACM]TL-Kruskal.doc》

下载本文的Word格式文档，以方便收藏与打印。

Copyright 2023. 昆居客 - IT编程,互联网信息技术文档大全!