【题解】P2573|【题解】P2573 [SCOI2012]滑雪（最小生成树）
发现了一道比较有思维的题，考虑记一下。
Desciption 给出 \(n\) 个点，每个点有一个高度，同时给出 \(m\) 条滑道。连接两个点，可以从高度高的点到高度低的点，滑道距离会给出。
求出能到达的所有点的最小滑道距离和。
Solution 【【题解】P2573|【题解】P2573 [SCOI2012]滑雪（最小生成树）】我们考虑一下，对于滑道我们可以建边，但是要注意。只能从高向低连边，同时相同高度的点之间得连双向边。
讲道理，我们发现这题说什么到所有可以到达的点的什么距离和，一看就是最小生成树。
那么我们考虑对于这么一张图我们先bfs出所有可以到达的点，然后再对他进行最小生成树。
但是有可能有些边是单向的我们怎么办？
其实有一个很神奇的想法，我们可以按照高度为第一关键字排个序，然后发现在高度低的之前，高度高的一定已经考虑过了，那么一定可以到达那些低的点。
具体怎么理解呢？
我们考虑这样建模，高度相同的点放在同一层，然后每次在一层做完最小生成树，通过连向下一层的边把答案继承到下一层。
具体实现的话可以通过对边连出的点的高度排序。
代码来了~~
#include
using namespace std;
#define int long longint En;
typedef pair PII;
const int N=1e5+5,M=1e6+5;
int head[N],height[N],fa[N],vis[N];
queue q;
vector G[N];
struct edge {
int x,y,w;
bool operator < (const edge &nt) const {
if(height[y]!=height[nt.y]) return height[y]>height[nt.y];
return wheight[v])
G[u].push_back(make_pair(v,w));
if(height[u] 转载于:https://www.cnblogs.com/JCNL666/p/11191573.html
推荐阅读
- 宽容谁
- 我要做大厨
- 增长黑客的海盗法则
- 画画吗（）
- 2019-02-13——今天谈梦想（）
- 远去的风筝
- 三十年后的广场舞大爷
- 叙述作文
- 20190302|20190302 复盘翻盘
- 学无止境，人生还很长