kruskal 的经典写法 通畅工程之类的题目的模板 最小生成树

主要是给编码看一下这种风格。

主要用了并查集和克鲁斯卡尔最小生成树的算法。

#include <iostream>
#include <algorithm>
#include<cstdio>
#include <stack> 
#include <fstream> 
#include <cstring>
#include <string>
#include <set>
#include <queue> 
#include <map>
using namespace std;
const int maxn=1e3+10;

int V,E;
template<typename T>
void showArray(T array){
	for(int i=1;i<=V;i++)
		cout<<array[i]<<" ";
	cout<<endl;
}
template<typename T>
void showMetrix(T metrix){
	for(int i=1;i<=V;i++){
		for(int j=1;j<=V;j++)
			cout<<metrix[i][j]<<" ";
		cout<<endl;
	}
	cout<<endl;
}

struct Edge{
	int start,end,val;
	Edge():start(-1),end(-1),val(-1){}
	bool operator<(Edge b){
		return val<b.val;
	}
}edge[maxn*3];

int pre[maxn];

int Find(int x){
//	cout<<"!"<<x<<pre[x]<<endl;
	if(x==pre[x]) return x;
	return pre[x]=Find(pre[x]);
}
void Union(int a,int b){
	int A=Find(a);
	int B=Find(b);
	if(A!=B) pre[a]=b;
}
int main(){
	while(cin>>V>>E){
		int s,e,val;
		for(int i=0;i<E;i++){
			cin>>s>>e>>val;
			edge[i].start=s;
			edge[i].end=e;
			edge[i].val=val;
		}
		for(int i=0;i<V;i++) pre[i]=i;
		
		sort(edge,edge+E);
		int cost=0;
		int cnt=0;
		for(int i=0;i<E;i++){
			int A=Find(edge[i].start);
			int B=Find(edge[i].end);
			if(A!=B){
				pre[A]=B;//union
				cost+=edge[i].val;
				cnt++;
			}
		}
		
		if(cnt!=V-1) cout<<-1<<endl;
		else cout<<cost<<endl;
		
	}
}