1.kruskal

• 最小生成树能够保证首先是树（对于n个顶点的图只有条n - 1边），其次保证任意两个顶点之间都可达，再次保证这棵树的边权值之和为最小，但不能保证任意两点之间是最短路径；（最后求出来的路径长度是经过n个顶点的)
• 最小生成树是到一群点（所有点）的路径代价和最小，是一个n - 1 条边的树，最短路是从一个点到另一个点的最短路径；

求最大生成树（所有点的路径代价之和最大）即把边从大到小排序

#include <bits/stdc++.h>
using namespace std;
const int N=1e3;
const int inf=0x3f3f3f3f;

struct node
{
    int u,v,w;
    bool operator <(const node &a)const
    {
        return w<a.w;
    }
}edge[N];

int father[N];
int n,m;

void init()
{
    for(int i=0;i<m;i++)
        father[i]=i;
}

int Find(int x)
{
    if(x==father[x])
        return x;
    return father[x]=Find(father[x]);
}

void Union(int x,int y)
{
    int tmpx=Find(x);
    int tmpy=Find(y);
    if(tmpx!=tmpy)
    {
        father[tmpx]=tmpy;
    }
}

int kruskal()
{
    sort(edge,edge+n);
    init();
    node now;
    int ans=0;
    for(int i=0;i<n;i++)
    {
        now=edge[i];
        if(Find(now.u)!=Find(now.v))
        {
            Union(now.u,now.v);
            ans+=now.w;
        }
    }
    return ans;
}

int main()
{
    while(scanf("%d%d",&n,&m)!=EOF&&n)
    {
        for(int i=0;i<n;++i)
        {
            scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);
        }
        int ans=kruskal();
        bool f=0;
        for(int i=2;i<=m;i++)
        {
            if(Find(1)!=Find(i))
            {
                f=1;
                break;
            }
        }
        if(f)
            cout<<"?"<<'\n';
        else
            cout<<ans<<'\n';
    }
    return 0;
}

2.prim

#include <bits/stdc++.h>
using namespace std;
const int N=1e3;
const int inf=0x3f3f3f3f;
int n,m;
int dis[N],vis[N],g[N][N];
int prim(int src)
{
    for(int i=1;i<=m;i++)
    {
        dis[i]=g[src][i];
    }
    int sum=0;
    vis[src]=1;
    dis[src]=0;
    for(int i=2;i<=m;i++)
    {
        int pos=-1;
        int minn=inf;
        for(int j=1;j<=m;j++)
        {
            if(dis[j]<minn&&!vis[j])
            {
                pos=j;
                minn=dis[j];
            }
        }
        if(pos==-1)
        {
            return -1;
        }
        sum+=minn;
        vis[pos]=1;
        for(int j=1;j<=m;j++)
        {
            if(!vis[j]&&dis[j]>g[pos][j])
            {
                dis[j]=g[pos][j];
            }
        }
    }
    return sum;
}
int main()
{
    int a,b,c;
    while(scanf("%d%d",&n,&m)!=EOF&&n)
    {
        memset(g,inf,sizeof(g));
        memset(dis,inf,sizeof(dis));
        memset(vis,0,sizeof(vis));
        for(int i=0;i<n;i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            if(c<g[a][b])
                g[a][b]=g[b][a]=c;
        }
        int ans=prim(1);
        if(ans==-1)
            cout<<"?"<<'\n';
        else
            cout<<ans<<'\n';
    }
    return 0;
}