Description
题目描述
a180285 非常喜欢滑雪。他来到一座雪山，这里分布着 m 条供滑行的轨道和 n 个轨道之间的交点（同时也是景点），
而且每个景点都有一编号 (1≤i≤n) 和一高度 h_i?。
a180285 能从景点 ii 滑到景点 j 当且仅当存在一条 i 和 j 之间的边，且 i 的高度不小于 j。
与其他滑雪爱好者不同，a180285 喜欢用最短的滑行路径去访问尽量多的景点。如果仅仅访问一条路径上的景点，他会觉得数量太少。
于是 a180285拿出了他随身携带的时间胶囊。这是一种很神奇的药物，吃下之后可以立即回到上个经过的景点
（不用移动也不被认为是 a180285 滑行的距离）。
请注意，这种神奇的药物是可以连续食用的，即能够回到较长时间之前到过的景点（比如上上个经过的景点和上上上个经过的景点）。
现在，a180285站在 1 号景点望着山下的目标，心潮澎湃。他十分想知道在不考虑时间胶囊消耗的情况下，
以最短滑行距离滑到尽量多的景点的方案（即满足经过景点数最大的前提下使得滑行总距离最小）。
你能帮他求出最短距离和景点数吗？
输入格式
输入的第一行是两个整数 n,m。 接下来一行有 n 个整数 h_i?，分别表示每个景点的高度。
接下来 m 行，表示各个景点之间轨道分布的情况。
每行三个整数 u,v,k，表示编号为 u 的景点和编号为 v 的景点之间有一条长度为 k 的轨道。
输出格式
输出一行，表示 a180285 最多能到达多少个景点，以及此时最短的滑行距离总和。
Solution
我们先按照给定标准连边。
时间胶囊可以让XXX不需要滑行距离地退回上一个景点且无限
容易发现我们要求一颗从1出发有向的生成树，使树中节点数最多的条件下边权和最小。
与Prim算法解决的问题契合
任意一棵最小生成树一定包含无向图中边权最小的边
给定一张无向图 G = （V，E），n = |V|，m = |E|。从 E 中选出 k < n-1条边构
成 G 的一个生成森林。若再从剩余的 m - k 条边中选出 n - 1 - k 条添加到生成森林
中，使其成为 G 的生成树，并且选出的边的权值之和最小，则该生成树一定包含这
m - k 条边中连接森林的两个不连通节点的权值最小的边
基于上述推论，有了 Prim 算法，它总是维护最小生成树的一部分。
起初， Prim 算法仅确定 1 号节点属于最小生成树。
在任意时刻，设已经确定属于最小生成树的节点集合为 T ，剩余节点集合为 S。
Prim算法找到min{z}（x属于S，y属于T），即两个端点分别属于集合 S,T 的权值最小的边，
然后把点 x 从集合 S 中删除，加入到集合 T 中，并把 z 累加到答案中。
另外，在 x 的时候用堆优化（思想同Dijkstra），可以将复杂度优化到O（mlogn）。
在此题中，由于第一条件是要有最多的点在树中，所以在堆中应优先以 x 的高度从高到低排序
以保证所有点都可以达到
Code
#include <cstdio> #include <cstdlib> #include <algorithm> #include <vector> #include <cstring> #include <queue> #define ll long long using namespace std; const int N=1e5+10,M=2e6+10; int u,v,h[N],n,m,cnt; struct node { int v; ll w; bool operator <(const node &o)const { return h[v]==h[o.v]?w>o.w:h[v]<h[o.v]; } }; priority_queue <node> q; vector <node> link[N]; bool flag[N]; ll w,dis[N],ans; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&h[i]); for(int i=0;i<m;i++) { scanf("%d%d%lld",&u,&v,&w); if(h[u]>=h[v]) link[u].push_back((node){v,w}); if(h[v]>=h[u]) link[v].push_back((node){u,w}); } memset(dis,0x3f,sizeof(dis)); dis[1]=0; q.push((node){1,0}); while(!q.empty()) { int u=q.top().v; q.pop(); if(flag[u]) continue; flag[u]=true,cnt++; ans+=dis[u]; int size=link[u].size(); for(int i=0;i<size;i++) { node t=link[u][i]; if(dis[t.v]>t.w) dis[t.v]=t.w,q.push(t); } } printf("%d %lld\n",cnt,ans); return 0; }
原文：https://www.cnblogs.com/hsez-cyx/p/12322790.html