题目：BZOJ2753、洛谷P2573、codevs2399。
题目大意：给你一张带权有向图（由于存在高度限制，所以边是有向的），问你从1开始最多能深度优先遍历多少个点（使用时间胶囊即为回溯），在遍历最多点的情况下，使得所有经过的边的权值和最小（由于深度优先遍历，所以就是求“有向图的最小生成树”）。
解题思路：第一问很容易，深搜遍历即可。
在遍历的时候把有用的边记录下来。
第二问其实就是求最小生成树，但边是有向的，怎么办?
这里仍然可以使用Kruskal解决。
我们可以在对边排序的时候，以终点的高度为第一关键字，从大到小排，以边权为第二关键字，从小到大排。
要保证有向图的“最小生成树”正确，我们必须从高到低按次序遍历下来。
而以终点的高度从大到小排，就能保证所遍历的点一定是从大到小的，也就保证了答案的正确性。
然后Kruskal跑即可。
时间复杂度$O(mlog_2 m)$，时间限制5s，强的数据能在1s左右运行完。
注意答案会超出$2^{32}$，要用64位整数。
C++ Code：
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,h[100002],cnt,head[100002],fa[100002],cnt2,mxJD,head2[100002];
long long mxDS;
bool vis[100002];
int dad(int x){return fa[x]==x?x:fa[x]=dad(fa[x]);}
struct edge{
int from,to,dis,nxt;
bool operator<(const edge& rhs)const{
if(h[to]!=h[rhs.to])return h[to]>h[rhs.to];
return dis<rhs.dis;
}
}e[1000005<<1],e2[1000005<<1];
inline int readint(){
char c=getchar();
for(;!isdigit(c);c=getchar());
int d=0;
for(;isdigit(c);c=getchar())
d=(d<<3)+(d<<1)+(c^'0');
return d;
}
void dfs(int now){
vis[now]=true;
++mxJD;
for(int i=head[now];i;i=e[i].nxt){
e2[++cnt2]=(edge){e[i].from,e[i].to,e[i].dis,head2[e[i].from]};
head2[e[i].from]=cnt2;
if(!vis[e[i].to])dfs(e[i].to);
}
}
int main(){
memset(head,0,sizeof head);
cnt=cnt2=mxJD=mxDS=0;
n=readint(),m=readint();
for(int i=1;i<=n;++i)h[i]=readint(),fa[i]=i;
while(m--){
int u=readint(),v=readint(),t=readint();
if(h[u]>=h[v]){
e[++cnt]=(edge){u,v,t,head[u]};
head[u]=cnt;
}//NOT else
if(h[u]<=h[v]){
e[++cnt]=(edge){v,u,t,head[v]};
head[v]=cnt;
}
}
memset(head2,0,sizeof head2);
memset(vis,0,sizeof vis);
dfs(1);
printf("%d ",mxJD);
sort(e2+1,e2+cnt2+1);
for(int i=1;i<=cnt2;++i){
int a=dad(e2[i].from),b=dad(e2[i].to);
if(a!=b){
mxDS+=e2[i].dis;
fa[b]=a;
if(--mxJD<2)break;
}
}
printf("%lld
",mxDS);
return 0;
}