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

題意：要在一天之內(nèi)訪問所有的奶牛（路過一個(gè)點(diǎn)就必須停下來交談），并且最后需要選擇一個(gè)點(diǎn)睡上一覺（交談多一次）所需的花費(fèi)。

思路：我已經(jīng)弱到看不懂中文題了啊。樣例又是錯(cuò)的，數(shù)據(jù)范圍也是錯(cuò)的。遇到這種題目就GG。

其實(shí)就是你選擇一個(gè)點(diǎn)出發(fā)，走完所有點(diǎn)后必須回到這個(gè)點(diǎn)睡一覺（加多一次點(diǎn)權(quán)），因此選一個(gè)點(diǎn)權(quán)最小的出發(fā)就可以了。

因?yàn)槟阕叱鋈?#xff0c;必須走回來，而且必須訪問邊的兩點(diǎn)，所以一條邊的邊權(quán)就是（num[u] + num[v] + 2 * w）。num[]代表點(diǎn)權(quán)。

記得存點(diǎn)的數(shù)組要開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 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/fightfordream/p/6644077.html

總結(jié)

以上是生活随笔為你收集整理的蓝桥杯：安慰奶牛（最小生成树）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。