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

http://lx.lanqiao.cn/problem.page?gpid=T16

题意：要在一天之内访问所有的奶牛（路过一个点就必须停下来交谈），并且最后需要选择一个点睡上一觉（交谈多一次）所需的花费。

思路：我已经弱到看不懂中文题了啊。样例又是错的，数据范围也是错的。遇到这种题目就GG。

其实就是你选择一个点出发，走完所有点后必须回到这个点睡一觉（加多一次点权），因此选一个点权最小的出发就可以了。

因为你走出去，必须走回来，而且必须访问边的两点，所以一条边的边权就是（num[u] + num[v] + 2 * w）。num[]代表点权。

记得存点的数组要开1e5。

正确的样例：

5 6
10
10
20
6
30
1 2 5
2 3 5
2 4 12
3 4 17
2 5 15
3 5 6
answer : 178

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define N 100010
 4 typedef long long LL;
 5 struct Edge {
 6     int u, v, nxt, w;
 7     bool operator < (const Edge &a) { return w < a.w; }
 8 } edge[N*2];
 9 int fa[N], head[N], tot, num[N]; LL ans;
10 void Add(int u, int v, int w) {
11     edge[tot] = (Edge) { u, v, head[u], w }; head[u] = tot++;
12     edge[tot] = (Edge) { v, u, head[v], w }; head[v] = tot++;
13 }
14 int Find(int x) { if(fa[x] == x) return x; return fa[x] = Find(fa[x]); }
15 void Merge(int x, int y) { x = Find(x), y = Find(y); if(x != y) fa[x] = y; }
16 void Kruskal(int n) {
17     sort(edge, edge + tot); int cnt = 0;
18     for(int i = 0; i < tot; i++) fa[i] = i;
19     for(int i = 0; i < tot; i++) {
20         int u = edge[i].u, v = edge[i].v, w = edge[i].w;
21         if(Find(u) == Find(v)) continue;
22         Merge(u, v); ans += w;
23     }
24 }
25 int main() {
26     int n, p; scanf("%d%d", &n, &p);
27     ans = 1000000000;
28     for(int i = 1; i <= n; i++) {
29         scanf("%d", &num[i]); ans = min(ans, (LL)num[i]);
30     }
31     memset(head, -1, sizeof(head)); tot = 0;
32     for(int i = 1; i <= p; i++) {
33         int u, v, w; scanf("%d%d%d", &u, &v, &w);
34         Add(u, v, w * 2 + num[u] + num[v]);
35     }
36     Kruskal(n);
37     cout << ans << endl;
38 }