这个题一看就是最小生成树，但是这题关键是确定边权。
首先为了安慰奶牛，一定要遍历每个奶牛并且回到起点，所以每条边会被经过两次，而为了通过这条边必须和两端点奶牛谈话，因此要再加上两端点的c值。综上(i,j)边权为l(i,j) * 2 + c_i + c_j。
#include#include #include #include #define N 10010#define M 10000000using namespace std;int n,m;struct qwq{ int x,y,val; bool operator < (const qwq &a) const { return val < a.val; }}e[M];int fa[N],siz[N];int find(int x){ if(fa[x] != x) fa[x] = find(fa[x]); return fa[x];}void merge(int x,int y){ if(siz[x] > siz[y]) swap(x,y); siz[y] += siz[x]; fa[x] = y; return;}int kruskal(){ sort(e + 1,e + 1 + m); int tot = 0,ans = 0; for(int i = 1;i <= m;i++) { int x = find(e[i].x),y = find(e[i].y); if(x != y) { merge(x,y); ans += e[i].val; tot++; } if(tot == n - 1) break; } return ans;}int c[N];using namespace std;int main(){ scanf("%d %d",&n,&m); int minn = 1000000; for(int i = 1;i <= n;i++) { scanf("%d",&c[i]); minn = min(c[i],minn); fa[i] = i; siz[i] = 1; } for(int i = 1;i <= m;i++) { scanf("%d %d %d",&e[i].x,&e[i].y,&e[i].val); e[i].val = (e[i].val << 1) + c[e[i].x] + c[e[i].y]; } printf("%d\n",kruskal() + minn); return 0;}