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

“村村通“是国家一个系统工程，其包涵有：公路、电力、生活和饮用水、电话网、有线电视网、互联网等等。

村村通公路工程，是国家为构建和谐社会，支持新农村建设的一项重大举措，是一项民心工程。又称“五年千亿元”工程

该工程是指中国力争在5年时间实现所有村庄通沥青路或水泥路，以打破农村经济发展的交通瓶颈，解决9亿农民的出行难题。

现有村落间道路的统计数据表中，列出了有可能建设成标准公路的若干条道路的成本，求使每个村落都有公路连通所需要的最低成本。

要求用Krusk al算法求解

#include&lt;bits/stdc++.h&gt;
using namespace std;
struct line
{
    //记录边连接的两个点 且s1的下标比s2的下标小
    string s1,s2;
    //记录边的长度
    int path;
}lines[205];
//将边按照权值从小到大排序
bool cmp(line l1,line l2)
{
    return l1.path&lt;l2.path;
}
//判断两个点是否不在同一个连通分量
bool judge(int home[],int index,map&lt;string,int&gt; m)
{
    string s1=lines[index].s1;
    string s2=lines[index].s2;
    int a1=m[s1];
    int a2=m[s2];
    if(home[a1]==home[a2]) return 0;
    else return 1;
}
//更新home值
void changeHome(int home[],int ini,int fin,int n)
{
    for(int i=0;i<n;i++)
    {
        if(home[i]==ini) home[i]=fin;
    }
}
int main()
{
    int n;
    cin&gt;&gt;n;
    //记录节点
    string s[205];
    //记录节点的下标
    map<string,int&gt; m;
    for(int i=0;i<n;i++) 
    {
        cin&gt;&gt;s[i];
        m[s[i]]=i;
    }

    int line;
    cin&gt;&gt;line;
    for(int i=0;i<line;i++)
    {
        string s1,s2;
        int k;
        cin>>s1>>s2>>k;
        if(m[s1]<m[s2])
        {
            lines[i].s1=s1;
            lines[i].s2=s2;
        }
        else
        {
            lines[i].s1=s2;
            lines[i].s2=s1;
        }
        lines[i].path=k;
    }

    //将边按照权值从小到大排序
    sort(lines,lines+line,cmp);
    //记录所在连通分量 用该连通分量内最小的下标表示
    int home[205];
    for(int i=0;i<n;i++) home[i]=i;
    int index=0;
    int i;
    int res=0;
    string ans="";
    for(i=0;i<n-1;i++)
    {
        //judge判断两个点是否不在同一个连通分量
        while(index<line&amp;&amp;!judge(home,index,m)) index++;
        if(index==line) break;
        int a1=m[lines[index].s1];
        int a2=m[lines[index].s2];
        if(home[a1]>home[a2]) swap(a1,a2);
        //更新home值
        changeHome(home,home[a2],home[a1],n);
        res+=lines[index].path;
        ans=ans+lines[index].s1+" "+lines[index].s2+" "+to_string(lines[index].path)+"n";
        index++;
    }
    if(i<n-1) cout<<"-1"<<endl;
    else
    {
        cout<<res<<endl;
        cout<<ans;
    }
    return 0;
}