dfs-bfs|bzoj2753 [SCOI2012]滑雪与时间胶囊各省省选|巧妙的做法|最小生成

传送门
Description
【dfs-bfs|bzoj2753 [SCOI2012]滑雪与时间胶囊】a180285非常喜欢滑雪。他来到一座雪山，这里分布着M条供滑行的轨道和N个轨道之间的交点（同时也是景点），而且每个景点都有一编号i（1<=i<=N）和一高度Hi。a180285能从景点i 滑到景点j 当且仅当存在一条i 和j 之间的边，且i 的高度不小于j。与其他滑雪爱好者不同，a180285喜欢用最短的滑行路径去访问尽量多的景点。如果仅仅访问一条路径上的景点，他会觉得数量太少。于是a180285拿出了他随身携带的时间胶囊。这是一种很神奇的药物，吃下之后可以立即回到上个经过的景点（不用移动也不被认为是a180285 滑行的距离）。请注意，这种神奇的药物是可以连续食用的，即能够回到较长时间之前到过的景点（比如上上个经过的景点和上上上个经过的景点）。现在，a180285站在1号景点望着山下的目标，心潮澎湃。他十分想知道在不考虑时间胶囊消耗的情况下，以最短滑行距离滑到尽量多的景点的方案（即满足经过景点数最大的前提下使得滑行总距离最小）。你能帮他求出最短距离和景点数吗？
Input
输入的第一行是两个整数N，M。
接下来1行有N个整数Hi，分别表示每个景点的高度。
接下来M行，表示各个景点之间轨道分布的情况。每行3个整数，Ui，Vi，Ki。表示编号为Ui的景点和编号为Vi的景点之间有一条长度为Ki的轨道。
Output
输出一行，表示a180285最多能到达多少个景点，以及此时最短的滑行距离总和。
Sample Input
3 3
3 2 1
1 2 1
2 3 1
1 3 10
Sample Output
3 2
HINT
【数据范围】

对于30%的数据，保证 1<=N<=2000 对于100%的数据，保证 1<=N<=100000

对于所有的数据，保证 1<=M<=1000000，1<=Hi<=1000000000，1<=Ki<=1000000000。
Source
题解第一眼看到这题以为就是一道bfs+MST的裸题，然而事实却并不是这么简单。究其原因，我还是对各种算法的理解程度和深度不够啊！
普通的Kruscal的适用范围是不分层的无向图，而这道题出现了分层图、有向边，于是翻了一下别人的题解，终于明白了这题的含义。
这道题虽然是有关MST的题目，但是并不能直接用处理MST的算法做。我们应将题目抽象成一个分层图，其中不同的层内部有一些边，不同的层内部也有一些边，但是方向均为由高处指向低处。这就需要我们在加边的时候保证边的方向是合理的。这样，在bfs的时候，只要有一条边指向一个未到达过的点，那这个点一定是可以到达的，因为我们没有加入由低到高的边。
Kruscal的第一步是排序，但我们不能仅仅按照长度排序。为了保证在构建MST的过程中由高层向低层构建，我们要先对边的终点由高到低排序，当终点的高度一样时再按照长度排序。
这样的题目要多画图想想，仅仅是思考有时很难得出正确的结论。
CODE：

#include #include using namespace std; struct queue { int h,t; int a[1000001]; inline void clear(){h=1,t=0; } inline void push(int n){a[++t]=n; } inline int front(){return a[h]; } inline void pop(){h++; } inline bool empty(){return h>t; } }q; struct edge { int from,next,to,dis; }a[2000001]; int h[1000001]; int f[1000001]; int head[1000001]; bool b[1000001]; int n,m,x,y,z,num,tot,k; long long dis; inline void add(int x,int y,int z) { a[++num].next=head[x],a[num].from=x,a[num].to=y,a[num].dis=z,head[x]=num; } inline bool cmp(edge a,edge b) { if(h[a.to]!=h[b.to]) return h[a.to]>h[b.to]; return a.dis=h[y]) add(x,y,z); if(h[y]>=h[x]) add(y,x,z); } bfs(); sort(a+1,a+num+1,cmp); for(int i=1; i<=num; i++) { if(!b[a[i].from]||!b[a[i].to]) continue; x=find(a[i].from),y=find(a[i].to); if(f[y]!=x) { f[y]=x; dis+=a[i].dis; k++; if(k==q.t-1) break; } } printf("%d %lld",q.t,dis); return 0; }