P1546 最短网络 Agri-Net 最小生成树 prim kruskal

题目：P1546 最短网络 Agri-Net

kruskal代码：

#include<bits/stdc++.h>
using namespace std;
#define maxl 100000
int n,a[110][110],f[110],sum=0;

struct Edge{
	int st,en,w;
}e[10010];
bool cmp(Edge x1,Edge x2){
	return x1.w<x2.w;
}

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

int main(){
	std::ios::sync_with_stdio(false);
	
	cin>>n;
	int x,y,w,t=0;
	for(int i=0;i<n;i++) 
	    for(int j=0;j<n;j++){
	    	cin>>w;
	    	e[t].st=i;e[t].en=j;e[t].w=w;
	    	t++;
		}
	for(int i=0;i<n;i++){
		f[i]=i;
	}
	sort(e,e+t,cmp);
	for(int i=0;i<t;i++){
		x=find(e[i].st),y=find(e[i].en),w=e[i].w;
		if(x!=y){
			f[x]=y;
			sum+=w;
			n--;
		}
		if(n==1){
			cout<<sum<<endl;
			return 0;
		}
	}
	
	return 0;
}

prim代码（和dijkstra算法大致相同）：

#include<bits/stdc++.h>
using namespace std;
#define maxl 100000
int n,g[110][110],sum=0;
int d[110],vis[110];
void prim(){
	priority_queue< pair<int ,int > , vector<pair<int ,int > >,greater<pair<int ,int > > > q;
	for(int i=0;i<n;i++){
		d[i]=0x3f3f3f3f;
	}
	q.push( make_pair(0,0) );
	while(!q.empty()){
		int x=q.top().first,y=q.top().second;
		q.pop();
		if(vis[y]) continue;
		vis[y]=1;
		sum+=x;
		for(int i=0;i<n;i++){
			if(g[y][i]&&d[i]>g[y][i]&&!vis[i]){
				d[i]=g[y][i];
				q.push( make_pair(d[i],i) );
			}
		}
	}
}

int main(){
	std::ios::sync_with_stdio(false);
	
	cin>>n;
	int x,y,w,t=0;
	for(int i=0;i<n;i++) 
	    for(int j=0;j<n;j++){
	    	cin>>w;
	    	g[i][j]=w;
		}
	prim();
	cout<<sum<<endl;
	return 0;
}