最小生成树知识点

prim算法

int k(int n,int m){
if(m>n)
	swap(n,m);
return m==1?n:k(m,n%m);
}

int prim()
{
    memset(dist,0x3f,sizeof dist);
    int res=0;
    
    for(int i=0;i<n;i++)
    {
        int t=-1;
        for(int j=1;j<=n;j++)
        if(!st[j]&&(t==-1 || dist[t] > dist[j] )) t=j;
        
        st[t]=true;
        
        if(i) res+=dist[t];
        if(i&&dist[t]==INF) return INF;
        
        for(int j=1;j<=n;j++) dist[j]=min(dist[j],g[t][j]);
    }
    return res;
}

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2022;
const int INF=0x3f3f3f3f;
int g[N][N],dist[N];
bool st[N];//是否访问过
int n,m;
int prim()
{
    memset(dist,0x3f,sizeof dist);
    int res=0;
    
    for(int i=0;i<n;i++)
    {
        int t=-1;
        for(int j=1;j<=n;j++)//在所有节点中
        if(!st[j]&&(t==-1 || dist[t] > dist[j] )) t=j;//第一个节点或者距离更小，更新节点选择
        
        st[t]=true;//设置该节点为已访问
        
        if(i) res+=dist[t];//如果不是第一个，结果加上该节点距离
        if(i&&dist[t]==INF) return INF;//如果所有边的最短边是INF，一定是INF
        
        for(int j=1;j<=n;j++) dist[j]=min(dist[j],g[t][j]);//更新所有节点距集合距离为加上新节点的距离
    }
    return res;
}
int main(void)
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i==j) g[i][j]=0;
            else g[i][j]=INF;
        }
    }
    for(int i=1;i<=2021;i++)
    {
        for(int j=1;j<=2021;j++)
        {
            if(i!=j)
            {
                int a=i,b=j;
                int sum=0;
                while(a||b)
                {
                    if(a%10!=b%10) sum+=a%10+b%10;
                    a/=10,b/=10;
                }
                g[i][j]=sum;
                g[j][i]=sum;
            }
        }
    }//邻接矩阵建边
    int t=prim();
    cout<<t<<endl;
    return 0;
}