HippopmonkeyHippopmonkeyHippopmonkey MST模板 MST模板

#define maxn 105
#define inf 0x3f3f3f3f
using namespace std;
int g[maxn][maxn];
int lowcost[maxn];
int visit[maxn];
int n;     
int (){
    int Min,mincost=0,next;
    memset(visit,0,sizeof(visit));
    for(int i=1;i<=n;i++){
        lowcost[i]=g[1][i];
    }
    visit[1]=1;
    for(int i=1;i<n;i++){
        Min=inf;
        for(int j=1;j<=n;j++){
            if(!visit[j] && Min>lowcost[j]){
                Min=lowcost[j];
                next=j;
            }
        }
        mincost+=Min;
        visit[next]=1;
        for(int j=1;j<=n;j++){
            if(!visit[j] && lowcost[j]>g[next][j]){
                lowcost[j]=g[next][j];
            }
        }
    }
    return mincost;
}
int main(){
//    freopen("input.txt","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    while(cin>>n){
        memset(g,inf,sizeof(g));
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                cin>>g[i][j];
            }
        }
        int cost=prime();
        cout<<cost<<endl;    
    }
    return 0;
}
//
6 10  
1 2 6  
1 3 1  
1 4 5  
2 3 5  
2 5 3  
3 4 5  
3 5 6  
3 6 4  
4 6 2  
5 6 6 
answer:15

#define maxn 100000
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
struct edge{
	int u,v,w;
	edge(int u,int v,int w):u(u),v(v),w(w){}
	bool operator < (const edge& x) const{
		return w<x.w;
	}
};
int n,m;
int p[maxn];
vector<edge>e;
int find(int x){
	return x==p[x]?x:p[x]=find(p[x]);
}
int kruskal(){
	int ans=0;
	int cnt=0;
	sort(e.begin(),e.end());
	for(int i=0;i<=n;i++) p[i]=i;
	for(int i=0;i<m;i++){
		int x=find(e[i].u),y=find(e[i].v);
		if(x!=y){
			ans+=e[i].w;
			p[x]=y;
			cnt++;
		}
		if(cnt==n-1) break;
	}
	return ans;
}
int main(){
//	freopen("input.txt","r",stdin);
//	freopen("ouput.txt","w",sdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		e.pb(edge(u,v,w));
	}
	cout<<kruskal()<<endl;
	return 0;
}
//
6 10  
1 2 6  
1 3 1  
1 4 5  
2 3 5  
2 5 3  
3 4 5  
3 5 6  
3 6 4  
4 6 2  
5 6 6 
answer:15