蓝桥杯-安慰奶牛（最小生成树kruskal）

题目大意：n只奶牛，p条路，管理员想削减路，只保留能保证牧场连通性的n-1条路。削减完后奶牛很伤心需要安慰，于是管理员需要选出耗时最少的路线 去安慰奶牛们。

输入包括安慰每只奶牛所需时间c[i]，以及走每条路所需时间。

要求输出你最终选出路线所需花费的时间 （其中时间包括 管理员每天早晨起来和晚上睡前都要安慰所在牧场奶牛一次）

PS:这个 "管理员每天早晨起来和晚上睡前都要安慰所在牧场奶牛一次" 理解了很久。。。才想通，

思路：求最小生成树是肯定的，但是这里有个问题，用边权选出的生成树一定是最小的吗？不一定。  假如a、b、c共三个牧场，有a-b，a-c，b-c三条路，按照边权大小依次选得的是a-b，a-c，而b-c因为边权大没选中，但是牧场a的奶牛安慰时间比起b、c都要大，这样算下来，遍历三个牧场，从a走过时花费的时间可能比来回b-c路所要时间都要长。

所以，边权得修改。

事实上，走的每条路都要安慰一下路连接的两头奶牛，比如路线a-b-c，从a出发，由题意早晨起来要安慰一下它，所以总时间加上c[a]，依次再继续走路a-b，奶牛b，路b-c，牛c，路b-c，牛b，路a-b，晚上回到a，睡前安慰a一次。  可以发现，每条路都被走两次，而且每条路相当于还加上了两端奶牛的安慰时间。

所以把每条路的边权修改为2*time[a][b]+c[a]+c[b]，最后的总时间=每条路总时间+一个起点处奶牛的安慰时间。

（复习了一下kruskal。。。题量太少，还得继续刷题。。）

#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
struct Edge
{
    int x,y,v;
}e[100003];
int n,p;
int min_c ;
int f[10001];
bool cmp(const Edge a,const Edge b)
{
    return a.v<b.v;
}
int find(int x)
{
    if(f[x]==x) return x;
    else return f[x]=find(f[x]);//此处少了个压缩就超时了一个测试点。。
}
void kruskal()
{
    int sum=0;
    for(int i=0;i<p;i++)
    {
        int fx = find(e[i].x);
        int fy = find(e[i].y);
        if(fx!=fy)
        {
            sum += e[i].v;
            f[fy] = fx;
        }
    }
    printf("%d\n",sum+min_c);
}
int main()
{
    scanf("%d%d",&n,&p);
    int c[10003];
    min_c = 1001;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&c[i]);
        if(c[i]<min_c) min_c = c[i];
        f[i] = i;
    }
    int x,y,tmp;
    for(int i=0;i<p;i++)
    {
        scanf("%d%d%d",&e[i].x,&e[i].y,&tmp);
        e[i].v = c[e[i].x]+c[e[i].y]+2*tmp;//修改边权
    }
    sort(e,e+p,cmp);
    kruskal();
    return 0;
}