USACO: Cheering Up the Cows_2524. cheering up the cows-CSDN博客

本文链接：https://blog.csdn.net/Geterns/article/details/6112586

Cheering Up the Cows

Time Limit(Common/Java):1000MS/10000MS Memory Limit:65536KByte
Total Submit: 10 Accepted: 3

Description

Farmer John has grown so lazy that he no longer wants to continue maintaining the cow paths that currently provide a way to visit each of his N (5 ≤ N ≤ 10,000) pastures (conveniently numbered 1..N). Each and every pasture is home to one cow. FJ plans to remove as many of the P (N-1 ≤ P ≤ 100,000) paths as possible while keeping the pastures connected. You must determine which N-1 paths to keep.

Bidirectional path j connects pastures S_j and E_j (1 ≤ S_j ≤ N; 1 ≤ E_j ≤ N; S_j != E_j) and requires L_j (0 ≤ L_j ≤ 1,000) time to traverse. No pair of pastures is directly connected by more than one path.

The cows are sad that their transportation system is being reduced. You must visit each cow at least once every day to cheer her up. Every time you visit pasture i (even if you're just traveling through), you must talk to the cow for time C_i (1 ≤ C_i ≤ 1,000).

You will spend each night in the same pasture (which you will choose) until the cows have recovered from their sadness. You will end up talking to the cow in the sleeping pasture at least in the morning when you wake up and in the evening after you have returned to sleep.

Assuming that Farmer John follows your suggestions of which paths to keep and you pick the optimal pasture to sleep in, determine the minimal amount of time it will take you to visit each cow at least once in a day.

For your first 10 submissions, you will be provided with the results of running your program on a part of the actual test data.

Input

* Line 1: Two space-separated integers: N and P
* Lines 2..N+1: Line i+1 contains a single integer: C_i
* Lines N+2..N+P+1: Line N+j+1 contains three space-separated integers: S_j, E_j, and L_j

Output

* Line 1: A single integer, the total time it takes to visit all the cows (including the two visits to the cow in your sleeping-pasture)

Sample Input

5 7 10 10 20 6 30 1 2 5 2 3 5 2 4 12 3 4 17 2 5 15 3 5 6 4 5 12

Sample Output

176

Hint

Input details:
+-(15)-+ / / / / 1-(5)-2-(5)-3-(6)--5 / /(17) / (12)/ / /(12) 4------+
Output details: Keep these paths: 1-(5)-2-(5)-3 5 / / (12)/ /(12) *4------+Wake up in pasture 4 and visit pastures in the order 4, 5, 4, 2, 3, 2, 1, 2, 4 yielding a total time of 176 before going back to sleep.

Source

USACO Nov 08

思路：

此题真有意思，难点在等价权重的分析。

首先，要得到这样一个结论：从任意点历遍一棵树并回到该点，每条边会被走过两次，每个结点v会被走过degree(v)次，而且对于本题，起始结点多走一次——当然，我们就选择那个需要用最少时间的作为起始结点

接着便可以推论：最小生成树树算法中一条边的cost为：两端点时间+ 2 * 边长

剩下的工作就很简单啦，因为是稀疏图，用kruskal，辅助数组为堆和并查集

PS：说到这个并查集，第一次接触，犯了个大错误，刚刚看完书，自以为懂了，书里的代码都没先过一遍就自己写上了：前者是我的版本，由于多次重复查找，很容易导致TLE，后者每次查找的同时进行赋值，对于大数据来说，节省的时间简直就不是一个数量级的！

好吧这个题目不是在USACO页面拷的，3AC看起来有点囧 = =|||

int root[size]; int findRoot(int v){ while (root[v]) v = root[v]; return v; } int findRoot(int v){ if (root[v]) return root[v] = findRoot(root[v]); return root[v]; }

AC代码：

#include <iostream> #include <fstream> #include <cstdio> #include <cmath> #include <cstdlib> #include <cstring> #include <algorithm> using namespace std; //最小生成树的Kruskal算法 const int size = 100500; int realSize; struct edge{ int head, tail, cost; }; //堆 edge heap[size], temp; int curSize; inline void qSwap(edge &a, edge &b){ temp = a; a = b; b = temp; } inline int fath(int idx){ return (idx - 1) >> 1; } inline int left(int idx){ return (idx << 1) | 1; } inline int rght(int idx){ return (idx + 1) << 1; } void siftDw(int idx){ int tarIdx = idx; while (true){ if (left(idx) < curSize && heap[left(idx)].cost < heap[tarIdx].cost) tarIdx = left(idx); if (rght(idx) < curSize && heap[rght(idx)].cost < heap[tarIdx].cost) tarIdx = rght(idx); if (tarIdx ^ idx){ qSwap(heap[idx], heap[tarIdx]); idx = tarIdx; } else return; } } void siftUp(int idx){ while (idx){ if (heap[fath(idx)].cost > heap[idx].cost){ qSwap(heap[fath(idx)], heap[idx]); idx = fath(idx); } else return; } } //并查集 int root[size]; inline void inil(){ memset(root, 0, sizeof(root)); } inline int findRoot(int v){ if (root[v]) return root[v] = findRoot(root[v]); return v; } //kruskal int u, v, total; void kruskal(){ int count = 0; inil(); while (count != realSize - 1){ qSwap(heap[0], heap[-- curSize]); siftDw(0); u = findRoot(heap[curSize].head); v = findRoot(heap[curSize].tail); if (u ^ v){ total += heap[curSize].cost; root[u] = v; count ++; } } } // int Time[size + 1], mint; int main(){ // freopen("in.txt", "r", stdin); //重定向输入 // freopen("out.txt", "w", stdout);//重定向输出 int p; while (scanf("%d %d", &realSize, &p) != EOF){ mint = 100000; for (int i = 1; i <= realSize; i ++){ scanf("%d", Time + i); if (Time[i] < mint) mint = Time[i]; } curSize = 0; total = 0; while(curSize ^ p){ scanf("%d %d %d", &heap[curSize].head, &heap[curSize].tail, &heap[curSize].cost); heap[curSize].cost <<= 1; heap[curSize].cost += Time[heap[curSize].head]; heap[curSize].cost += Time[heap[curSize].tail]; siftUp(curSize ++); } kruskal(); printf("%d/n", total + mint); } // fclose(stdin); //关闭文件 // fclose(stdout); //关闭文件 return 0; }