题目
洛谷：P2573 [SCOI2012] 滑雪
分析
题目条件要点分析：
- 这道题要求 i 能到达 j 的前提是
i 、j 之间有一条连通的边并且i 的高度比 j 高。这意味着本题给出的是一个有向图。 - 时间胶囊可以返回到上一个景点，可以无限使用，意味着可以返回到之前经历过的任意一个景点。这意味这个有向图可以回溯，那便可以进行 dfs 或者 bfs 。
- “现在，a180285 站在 1 号景点望着山下的目标，心潮澎湃”，这句话表示 a180285 是从 1 号景点出发的，不能从其他地方出发。
问题分析：
题目要求出 “最多能到达多少个景点” 以及 “此时滑行的最短距离”。
- “最多能到达多少个景点”： 潜台词就是说本题中的这个图是非连通图，要求从 1 号景点出发最多能连通多少个景点。
- “此时滑行的最短距离”：求此时的最短距离，那么就是相当于求一个“最小生成树”，只不过在真正的最小生成树中要求：任意两顶点之间有且只有一条路径。而对于本题的这个“最小生成树”实际上它的每条边都是有方向的，因为只能从高顶点到低顶点。而时间胶囊的回溯功能又恰恰可以弥补这一点，所以这题是可以当成最小生成树来求的。
算法分析：
- 对于第一问求最多能到达多少个景点，直接用一个 dfs 来实现，看看有多少景点连通。如果要用 dfs 那么就要建图，这里使用 vector 数组实现孩子表示法来建图。
- 然后要求最短距离，我们使用 kruskal 算法来计算最小生成树的最小边权和，kruskal 算法是不需要建图的，它需要用一个数组统计所有边的信息，然后对边进行排序，依次拿出需要的边即可。那么现在虽然我们以及建图了，但是我们求最短路径不需要建图，我们需要记录边的信息，那怎么办呢？于是我们赋予 dfs 一个功能，在 dfs 的过程中再让 dfs 统计每条边的信息，方便后续进行 kruskal 算法。
代码
#include<iostream>
#include<algorithm>
#include<vector>using namespace std;typedef long long LL;
typedef pair<int,int> PII;const int N = 1e5 + 10, M = 2e6 + 10;int fa[N];
int h[N];
int n,m;
bool st[N];vector<PII> edge[N]; //存图，用来dfs int pos;
struct node
{int x,y,z; //结构体用来存每个点到下一个点的信息
}e[M]; //计算kruskal算法 LL cnt; //统计最多能到达多少个景点
LL ret; //此时最短的滑行距离总和 int find(int x)
{return fa[x] == x ? x : fa[x] = find(fa[x]);
}void dfs(int u)
{cnt++;st[u] = true;for(auto& p:edge[u]) //遍历u可以到达的地方 {int y = p.first, z = p.second; pos++;e[pos].x = u, e[pos].y = y, e[pos].z = z;if(!st[y]) dfs(y); }
}bool cmp(node& a, node& b)
{int y1 = a.y, z1 = a.z, y2 = b.y, z2 = b.z;if(h[y1] != h[y2]) return h[y1] > h[y2];else return z1 < z2;
}void kk()
{for(int i=1;i<=n;i++) fa[i] = i;sort(e + 1,e + 1 + pos, cmp);for(int i=1;i<=pos;i++) //循环到pos即可，不需要循环到m {int x = e[i].x, y = e[i].y, z = e[i].z;int fx = find(x), fy = find(y);if(fx != fy){ret += z;fa[fx] = fy;} }
}int main()
{cin >> n >> m;for(int i=1;i<=n;i++) cin >> h[i];//存图 for(int i=1;i<=m;i++){int x,y,z; cin >> x >> y >> z;//方向就是从高高低 if(h[x] >= h[y]) edge[x].push_back({y,z});if(h[y] >= h[x]) edge[y].push_back({x,z});}dfs(1); //dfs出最多能到达多少个景点，并且记录这个连通图的每条边的信息。 cout << cnt << " "; kk();cout << ret << endl;return 0;}
