滑雪与时间胶囊

题意

给定n个点，m条路径。每个点有个高度h，i可以到j，当且仅当h[i] >= h[j]，i和j之间有路径。求从1出发，最多可以经过几个点，其最短路径长度。（使用时间胶囊可以回到之前经过的点）

思路

第一问简单bfs一下就行。第二问如果没有h的限制就是一个最小生成树，然而有高度的限制就不太行了。进一步分析好像是求一个有向图的最小生成树（大雾）。我们再来看看kruskal算法，每次都是贪心的选取最短的边，因为这里有高度的限制，每条从1出发的路径高度都是非递增的，我们显然不能这么做。那我们可不可以把这个限制“去掉”呢？好像是可以的，对于 按从大到小排序，再按路径长度从小到大排，每次选的都是最高点，因此对于之后的选择高度就没有限制啦。

代码

#include<bits/stdc++.h>
using namespace std;


const int maxn = 1e5 + 10;
const int maxm = 1e6 + 10;

int n, m;
bool vis[maxn];
int f[maxn], h[maxn];

void I(int x){for(int i = 0; i <= x; i++) f[i] = i;}
int F(int x){return f[x] == x ? x : f[x] = F(f[x]);}
void U(int x, int y){f[F(x)] = F(y);}
bool S(int x, int y){return F(x) == F(y);}

struct Edge{
    int u, v;
    long long w;

    bool friend operator <(Edge a, Edge b){
        if(h[a.v] != h[b.v])
            return h[a.v] > h[b.v];
        return a.w < b.w;
    }
};


vector<int> g[maxn];
Edge e[maxm];
vector<Edge> E;


long long ans1, ans2;
void dfs(int i){
    vis[i] = 1, ans1++;
    for(int v : g[i]){
        if(vis[v] || (h[i] < h[v])) continue;
        dfs(v);
    }
}

void Kruskal(){
    long long cnt = 0;
    sort(E.begin(), E.end());
    for(auto it : E){
        if(!S(it.u, it.v)){
            U(it.u, it.v);
            ans2 += it.w;
            cnt ++;
        }

        if(cnt + 1 == ans1) break;
    }

}

int main()
{
    cin >> n >> m;
    I(n);
    for(int i = 1; i <= n; i++){
        cin >> h[i];
    }
    for(int i = 0; i < m; i++){
        scanf("%d %d %lld", &e[i].u, &e[i].v, &e[i].w);
        //cin >> e[i].u >> e[i].v >> e[i].w;  cin会超，亲测～～
        int u = e[i].u, v = e[i].v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    dfs(1);
    for(int i = 0; i < m; i++){
        int u = e[i].u, v = e[i].v, w = e[i].w;

        if(vis[u] && vis[v]){
            if(h[u] >= h[v]){
                E.push_back({u, v, w});
            }
            if(h[u] <= h[v]){
                E.push_back({v, u, w});
            }
        }
    }
    Kruskal();
    cout << ans1 << " " << ans2 << endl;

    return 0;
}