安慰奶牛

传送门 ：安慰奶牛

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>

using namespace std;

struct node{
    int x,y,w;
};  
 
node s[100010];//边 
int sum;//记录最小时间 
int f[10010];//表示各个顶点在不同的连通分量上。 (即所属父亲)
int talk[10010];// 记录 每个牧场的谈话时间 

void init()//初始化 
{
    int i;
    for(i=0;i<10010;i++)
        f[i]=i;
}

int cmp(node a,node b) //排序，从小到大 
{
    return a.w<b.w;
}

void kruscal(int n,int l)//kruscal 入口 
{
    int q;   
    sort(s,s+l,cmp);
    int num=1,j;  //记录边的个数 
    int k=0;//循环边的下标 
    while(num<n)
    {
        if(f[s[k].x]!=f[s[k].y]) //判断这条边是否构成回路 
        {
            num++;
            sum+=s[k].w;
            q=f[s[k].y];
            for(j=1;j<=n;j++)//循环每个和q相等的顶点父亲 .
            {
                if(f[j]==q)    f[j]=f[s[k].x];
            }
        }
        k++;//循环每条边 
    }
}
int main()
{
    
    int n,p,i;
    while(~scanf("%d%d",&n,&p))
    {
        init();
        sum=0;
        int min=99999;
        for(i=1;i<=n;i++)//找最小的顶点，从这一点出发 
        {
            scanf("%d",&talk[i]);
            if(min>talk[i])    min=talk[i];
        }
        for(i=0;i<p;i++)//构造可以生成最小树的连通图。 
        {
            scanf("%d%d%d",&s[i].x,&s[i].y,&s[i].w);
            s[i].w=talk[s[i].x]+talk[s[i].y]+2*s[i].w;
        }
        kruscal(n,p);
        printf("%d
",sum+min);
        //for(i=1;i<=n;i++) 最小生成树的顶点最后成为一个连通图，即f[i]都相等 
        //    cout << f[i]<<endl; 
    }
}