BZOJ1232: [Usaco2008Nov]安慰奶牛cheer(最小生成树)

题意:给一个图 需要找到一个子图使得所有点都连通

　　 然后再选择一个点做为起点 走到每个点并回到起点

　　 每条边，每个点被经过一次就要花费一次边权、点权

题解:肯定是找一颗最小生成树嘛

　　 然后惊奇的发现 任意选一个点做为一个起点遍历的答案都是 每条边走两次

　　 每个点度数是多少点权就统计几次 依题意起点多统计一次 那么起点就选一个点权最小的点

　　 然后把每条边两个端点的点权赋给它 跑一个最小生成树

　　 还是挺有意思的

#include <bits/stdc++.h>

using namespace std;

int val[];

int vis[];

int pre[];

struct node

{

    int u, v, w;

}E[];

bool cmp(node A, node B) {return A.w < B.w;}

int find(int x)

{

    if(x == pre[x]) return x;

    else return pre[x] = find(pre[x]);

}

int main()

{

    int cnt = ;

    int n, p;

    scanf("%d%d", &n, &p);

    for(int i = ; i <= n; i++) pre[i] = i;

    int ans = ;

    int tmp = ;

    for(int i = ; i <= n; i++) scanf("%d", &val[i]), tmp = min(tmp, val[i]);

    ans += tmp;

    for(int i = ; i <= p; i++)

    {

        int a, b, c; scanf("%d%d%d", &a, &b, &c);

        E[++cnt].u = a; E[cnt].v = b; E[cnt].w = c *  + val[a] + val[b];

    }

    sort(E + , E +  + cnt, cmp);

    int tot = ;

    for(int i = ; i <= cnt; i++)

    {

        if(tot == n - ) break;

        int ax = find(E[i].u);

        int bx = find(E[i].v);

        if(ax == bx) continue;

        tot++;

        ans += E[i].w;

        pre[ax] = bx;

    }

    printf("%d\n", ans);

    return ;

}