本文主要是介绍安慰奶牛 蓝桥真题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这个题关键在于怎么处理这些点需要重复到达的问题 题目要求最后只剩一个树图 即只留(n-1)条边 我们把每条边的边权乘二 再加上左右两节点的点权 作为新的边权 然后套克鲁斯卡尔 最后加上一个最小的点权
1. 边权乘二
那么对于每一条边edge[i] 它都连接了以左节点edge[i].u为根的子树(左树)和以右节点edge[i].v为根的子树(右树) 而题目要求最后必须回到出发点 那么假设我们出发点在左树 现在要经过edge[i]去遍历右树上的节点 去时走了一次edge[i] 因为要回到出发点 所以又走了一次edge[i] 所以这个一来一回是必不可少的 又因为我们返回时再次经过edge[i]时 肯定已经把右树节点都处理完毕(不然你回来干什么。。) 所以每条边必走两次且只走两次
2. 加上左右两节点的点权
设节点p 其邻接边有 a b c d
如果我们走a来到了p(一次访问) 现在要通过b c d去遍历其下的子树 因为要回到出发点 所以在回程时必经a各一次(b c d共三次)
所以每个节点有多少邻接点 即度为多少 那它就要被经过几次
可这些度是谁提供的呢 当然是边啊 无向图中每条边会为左右两个节点各贡献一个度 所以在这里我们就可以把这些点权附加到边权上了 这样就可以处理了
3. 加上一个最小的点权
出发时还要安慰出发点的那头牛 等于经过了一次出发点 但我们是突然出现在出发点的 无法在出发点的度上体现出来 所以必须单独考虑
不管我们把谁作为出发点 1 2条是不变的 所以哪个点权值小就把谁作为出发点
好啰嗦。。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 0x3f3f3f3f3f3f3f3fstruct node
{int u;int v;ll w;
};node edge[100010];
ll val[10010];
int f[10010];
int n,m;bool cmp(node n1,node n2)
{return n1.w<n2.w;
}int getf(int p)
{if(f[p]==p) return p;else{f[p]=getf(f[p]);return f[p];}
}bool unite(int u,int v)
{int fu,fv;fu=getf(u);fv=getf(v);if(fu!=fv){f[fv]=fu;return true;}else return false;
}int main()
{ll sum,minn;int i,cnt;scanf("%d%d",&n,&m);for(i=1;i<=n;i++){scanf("%lld",&val[i]);}for(i=1;i<=m;i++){scanf("%d%d%lld",&edge[i].u,&edge[i].v,&edge[i].w);edge[i].w=2*edge[i].w+val[edge[i].u]+val[edge[i].v];}for(i=1;i<=n;i++){f[i]=i;}sort(edge+1,edge+m+1,cmp);sum=0,cnt=0;for(i=1;i<=m;i++){if(unite(edge[i].u,edge[i].v)){sum+=edge[i].w,cnt++;}if(cnt==n-1) break;}minn=N;for(i=1;i<=n;i++){minn=min(minn,val[i]);}printf("%lld\n",sum+minn);return 0;
}
这篇关于安慰奶牛 蓝桥真题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
