最小生成树入门（克鲁斯卡尔+普利姆 hdu1233）

克鲁斯卡尔

#include <set>

#include <map>

#include <queue>

#include <stack>

#include <math.h>

#include <bitset>

#include <vector>

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#define MAXN 1010100

#define LL long long

#define fi first

#define se second

#define mp make_pair

#define pb push_back

#define ll __int64

#define INF 0x7fffffff

#define cs(s) freopen(s,"r",stdin)

#define mem(x) memset(x,0,sizeof(x))

#define PI acos(-1)

#define eps 1e-10

using namespace std;

int gcd(int a,int b){return b?gcd(b,a%b):a;}

int lcm(int a,int b){return a/gcd(a,b)*b;}

LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}

//head

int n,m;

int f[10001];

int find(int x){

	return x==f[x]?x:f[x]=find(f[x]);

}

struct uzi

{

	int l,r,w;

	bool operator <(const uzi & t)const {

		return w<t.w;

	}

};

vector<uzi>v;

void init(){

	v.clear();

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

}

int main(){

	// freopen("in.txt","r",stdin);

	// freopen("out.txt","w",stdout);

	ios::sync_with_stdio(false);

	while(cin>>n&&n){

		init();

		for(int i=1;i<=n*(n-1)/2;i++){

			int l,r,w;

			cin>>l>>r>>w;

			v.pb({l,r,w});

		}

		int sum=0,cnt=0;

		sort(v.begin(), v.end());

		for(int i=0;i<v.size();i++){

			uzi k=v[i];

			int x=find(k.l),y=find(k.r);

			if(x==y)continue;

			f[y]=x;

			sum+=k.w;

			if((++cnt)==n-1)break;

		}

		cout<<sum<<endl;

	}

	return 0;

}

普利姆

#include <set>

#include <map>

#include <queue>

#include <stack>

#include <math.h>

#include <bitset>

#include <vector>

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#define MAXN 1010100

#define LL long long

#define fi first

#define se second

#define mp make_pair

#define pi pair<int,int>

#define pb push_back

#define INF 0x7fffffff

#define cs(s) freopen(s,"r",stdin)

#define mem(x) memset(x,0,sizeof(x))

#define PI acos(-1)

#define eps 1e-10

using namespace std;

int gcd(int a,int b){return b?gcd(b,a%b):a;}

int lcm(int a,int b){return a/gcd(a,b)*b;}

LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}

//head

int t,n,m,s,w;

int a[101][101],vis[101],dis[101];

void gao(){

	for(int i=1;i<=n;i++)vis[i]=0,dis[i]=INF;

	dis[1]=0;

	int ans=0;

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

		int mark=-1;

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

			if(!vis[j]){

				if(mark==-1)mark=j;

				else if(dis[j]<dis[mark])mark=j;

			}

		}

		if(mark==-1)break;

		ans+=dis[mark];

		vis[mark]=1;

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

			if(!vis[j])dis[j]=min(dis[j],a[mark][j]);

		}

	}

	cout<<ans<<endl;

	return ;

}

int main(){

	ios::sync_with_stdio(false);

	while(cin>>n&&n){

		for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)a[i][j]=INF;

		for(int i=1;i<=n*(n-1)/2;i++)cin>>s>>t>>w,a[s][t]=a[t][s]=w;

		gao();

	}

	return 0;

}