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

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

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

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

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

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

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

　　 还是挺有意思的

 

#include 
      
       using namespace std;int val[10005];int vis[10005];int pre[10005];struct node{    int u, v, w;}E[200005];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 = 0;    int n, p;    scanf("%d%d", &n, &p);    for(int i = 1; i <= n; i++) pre[i] = i;    int ans = 0;    int tmp = 1005;    for(int i = 1; i <= n; i++) scanf("%d", &val[i]), tmp = min(tmp, val[i]);    ans += tmp;    for(int i = 1; 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 * 2 + val[a] + val[b];    }    sort(E + 1, E + 1 + cnt, cmp);    int tot = 0;    for(int i = 1; i <= cnt; i++)    {        if(tot == n - 1) 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 0;}