村村通工程（Prim算法）/最小生成树Prim算法【数据结构】

最小生成树：在一给定的无向图G = (V, E) 中，(u, v) 代表连接顶点 u 与顶点 v 的边，而 w(u, v) 代表此的边权重，若存在 T 为 E 的子集（即）且为无循环图，使得的 w(T) 最小，则此 T 为 G 的最小生成树。最小生成树其实是最小权重生成树的简称。（简而言之就是把一个图变成一棵树，并且树中的边权和最小，还能连接所有顶点）

Prim算法：其基本思想是对图G(V,E)设置集合S，存放已被访问的顶点，然后每次从集合V-S中选择与集合S的最短距离最小的一个顶点（记为u），访问并加入集合S。之后，令顶点u为中介点，优化所有从u能到达的顶点v与集合S之间的最短距离。这样的操作执行n次（n为顶点个数），直到集合S已包含所有顶点。
可以发现，prim 算法的思想与最短路径中Dijk str a 算法的思想几乎完全相同，只是在涉及最短距离时使用了集合S代替 Dijk str a 算法中的起点s。

#include&lt;bits/stdc++.h&gt;
#define INF 99999999;
using namespace std;
struct array
{
    //记录到达的最短距离是到集合中哪个点
    string connection;
    //记录到达集合S中的点的最短距离
    int r=INF;
}arr[205];
//对V-S集合更新
//index即新加的点的下标 now是新加的点
void change(int a[][205],string now,int index,int n)
{
    arr[index].r=0;
    for(int i=0;i<n;i++)
    {
        if(!arr[i].r||!a[index][i]) continue;
        if(a[index][i]<arr[i].r) 
        {
            arr[i].r=a[index][i];
            arr[i].connection=now;
        }
    }
}
int ans=0;
string res="";
//找到最短的一条路径返回其点
string cmp(int a[][205],int n,string s[])
{
    int small=INF-1;
    string name;
    string first;
    for(int i=0;i<n;i++)
    {
        if(arr[i].r!=0&amp;&amp;arr[i].r<small) 
        {
            small=arr[i].r;
            name=s[i];
            first=arr[i].connection;
        }
    }
    ans+=small;
    res=res+first+" "+name+" "+to_string(small)+"n";
    return name;
}
int main()
{
    int n;
    cin>>n;
    //记录顶点
    string s[205];
    //记录顶点的下标
    map<string,int> m;
    for(int i=0;i<n;i++) 
    {
        cin>>s[i];
        m[s[i]]=i;
    }
    int line;
    cin>>line;
    //邻接矩阵
    int a[205][205]={0};
    for(int i=0;i<line;i++)
    {
        string s1,s2;
        int k;
        cin>>s1>>s2>>k;
        int a1=m[s1];
        int a2=m[s2];
        a[a1][a2]=k;
        a[a2][a1]=k;
    }
    string sta;
    cin>>sta;
    int now=m[sta];
    for(int i=0;i<n-1;i++)
    {
        //对V-S集合更新
        change(a,sta,now,n);
        //找到最短的一条路径返回其点
        sta=cmp(a,n,s);
        now=m[sta];
    }
    cout<<ans<<endl;
    cout<<res;
    return 0;
}