問題描述

Farmer John變得非常懶，他不想再繼續維護供奶牛之間供通行的道路。道路被用來連接N個牧場，牧場被連續地編號為1到N。每一個牧場都是一個奶牛的家。FJ計劃除去P條道路中盡可能多的道路，但是還要保持牧場之間 的連通性。你首先要決定那些道路是需要保留的N-1條道路。第j條雙向道路連接了牧場Sj和Ej(1 <= Sj?<= N; 1 <= Ej?<= N; Sj?!= Ej)，而且走完它需要Lj的時間。沒有兩個牧場是被一條以上的道路所連接。奶牛們非常傷心，因為她們的交通系統被削減了。你需要到每一個奶牛的住處去安慰她們。每次你到達第i個牧場的時候(即使你已經到過)，你必須花去Ci的時間和奶牛交談。你每個晚上都會在同一個牧場(這是供你選擇的)過夜，直到奶牛們都從悲傷中緩過神來。在早上 起來和晚上回去睡覺的時候，你都需要和在你睡覺的牧場的奶牛交談一次。這樣你才能完成你的 交談任務。假設Farmer John采納了你的建議，請計算出使所有奶牛都被安慰的最少時間。

輸入格式

第1行包含兩個整數N和P。

接下來N行，每行包含一個整數Ci。

接下來P行，每行包含三個整數Sj, Ej和Lj。

輸出格式

輸出一個整數, 所需要的總時間(包含和在你所在的牧場的奶牛的兩次談話時間)。

樣例輸入

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

樣例輸出

176（數據有誤，應該是178）

數據規模與約定

5 <= N <= 10000，N-1 <= P <= 100000，0 <= Lj?<= 1000，1 <= Ci?<= 1,000。

題意：這道題其實本身不是特別難，主要就是題意難以理解，主要是計算安慰所有的牛最短的時間，所有的牧場中的牛要安慰一次，但是題意指出起始點的牛要安慰兩次。根據題意構造一顆最小生成樹即解決總的安慰時間最短，但是樹中的節點也存在權值，所以不能按照常規的套路來做，看了網上的許多老鐵做的方法，把2*邊的權值+邊連接兩點的安慰時長作為邊的新的權值，然后在使用最小生成樹的方法。藍橋杯的官網的錦囊也說了這個方法。

思路：用結構體保存兩點以及兩點之間新的權值，然后加入優先級隊列中，對<進行重載后，按照權值從小到大的順序排列，然后使用克魯斯卡爾算法解決總的時長。此算法中使用了并查集來解決問題，對于一顆最小生成樹，只有集合，對優先級隊列中的元素中包含的兩點依次判斷，判斷是否屬于一個集合中，不屬于一個集合要進行合并，此處合并對于小樹貼到大樹上的優點不明顯，和任意貼時間差不多，但是路徑壓縮還是需要的，樹一直長高會導致查找效率變低，所以要進行路徑壓縮。

我在最后就是發現在藍橋杯的OJ上不能使用system("pause");來使運行框暫停，會報錯一個測試點都通不過。所以一定不要手殘加了！！！

代碼1：小樹貼到大樹上

#include <iostream> #include<queue> #include<algorithm> #define N 10010 using namespace std; struct node {int u, v, dis;node(int u, int v, int d) :u(u), v(v), dis(d) {}friend bool operator < (const node &a, const node &b) {//重載小于運算負，使用優先級隊列 return a.dis > b.dis;} }; priority_queue<node> q; int cost[N],s[N]; int find(int x) {//尋找父節點,并且進行路徑壓縮 if (s[x] < 0)return x;else {return s[x] = find(s[x]);} } void Union(int u, int v) {//合并兩個節點 int rootU = find(u), rootV = find(v);if (rootU != rootV) {//操作的是對于根節點而而言的，if (s[rootU] < s[rootV]) {//值表示根節點的規模，將小的樹掛在大的樹上面 s[rootU] += s[rootV];s[rootV] = rootU;}else {s[rootV] += s[rootU];s[rootU] = rootV;}} } int kruskal() {//使用克魯斯卡爾算法計算最小生成樹，對于一顆最小生成樹而言，其任意兩點的父節點是相等的 int sumDis = 0;while (!q.empty()) {node tem = q.top();q.pop();int root1 = find(tem.u), root2 = find(tem.v);if (root1 != root2) {sumDis += tem.dis;Union(root1,root2);//將兩個點的合并成一個集合 }}return sumDis; } int main(int argc, char** argv) {fill(s, s + N, -1);//初始化所有節點的父節點 int n, p, a, b, c;cin >> n >> p;for (int i = 1; i <= n; i++) {//輸入所有節點的權值 scanf("%d", &cost[i]);}for (int i = 0; i < p; i++) {//輸入所有的節點以及所有的路徑 scanf("%d%d%d", &a, &b, &c);q.push(node{ a,b,(2 * c + cost[a] + cost[b]) }); //把路徑的兩倍+路徑上兩個節點的和作為邊的新權值 }int sumCost = kruskal();sumCost += *min_element(cost+1,cost+n);//min_element函數主要求出的是給定數組長度的最小值cout << sumCost << endl;return 0; }

代碼2：第一個點貼在第二個點上

#include <iostream> #include<queue> #include<algorithm> #define N 10010 using namespace std; struct node {int u, v, dis;node(int u, int v, int d) :u(u), v(v), dis(d) {}friend bool operator < (const node &a, const node &b) {//重載小于運算負，使用優先級隊列 return a.dis > b.dis;} }; priority_queue<node> q; int cost[N], mindis, s[N]; int find(int x) {//尋找父節點,并且進行路徑壓縮 if (s[x] < 0)return x;else {return s[x] = find(s[x]);} } int kruskal() {//使用克魯斯卡爾算法計算最小生成樹，對于一顆最小生成樹而言，其任意兩點的父節點是相等的 int sumDis = 0;while (!q.empty()) {node tem = q.top();q.pop();int root1 = find(tem.u), root2 = find(tem.v);if (root1 != root2) {sumDis += tem.dis;s[root1] = root2;}}return sumDis; } int main(int argc, char** argv) {fill(s, s + N, -1);//初始化所有節點的父節點 int n, p, a, b, c;cin >> n >> p;for (int i = 1; i <= n; i++) {//輸入所有節點的權值 scanf("%d", &cost[i]);}for (int i = 0; i < p; i++) {//輸入所有的節點以及所有的路徑 scanf("%d%d%d", &a, &b, &c);q.push(node{ a,b,(2 * c + cost[a] + cost[b]) }); //把路徑的兩倍+路徑上兩個節點的和作為邊的新權值 }int sumCost = kruskal();sumCost += *min_element(cost+1,cost+n);cout << sumCost << endl;return 0; }

?

總結

以上是生活随笔為你收集整理的蓝桥杯 ALGO-6 安慰奶牛的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。