Question

有1到n个景点，每个景点有一个高度h，从1号节点出发，求能到达多少个景点和最小生成树。

Solution

预处理有向边建图 Kruscal
这道题和普通的求最小生成问题的区别在于，这里是有向路，高度只能从高到低(可以相等)。
那我们需要从1号节点开始dfs预处理能够走得通的有向路，并将走得通的结点数量记录，再用Kruscal去求即可。

不知道是不是哪里写的有问题，没加O(2)+O(3)的情况下超时了，加了就过去了。
感觉应该是我没用不会链式前向星的而用Vector常数太大的缘故吧。

Code

#include<bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;
const int N = 1e5 + 5;

struct edge{int to,cost;}a[N];
vector<edge> G[N];
bool v[N];
ll cnt,tot,ans;
int n,m,h[N];

struct node{
    int to,from,cost;
    bool friend operator < (node A,node B) {
        if (h[A.to]!=h[B.to]) return h[A.to]<h[B.to];
        return A.cost>B.cost;
    }
}b;


int f[N];
void init(int n){for(int i=0;i<=n;i++) f[i]=i;}
inline int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
inline void merge(int x,int y){int u=find(x),v=find(y);if(u!=v) f[v]=u;}
inline bool check(int x,int y){return find(x)==find(y);}

priority_queue<node> q;

inline void build(int x){
    for(auto c:G[x]){
        b.to=c.to,b.cost=c.cost,b.from=x;
        q.push(b);
        if(!v[c.to]) v[c.to]=true,build(c.to),cnt++;
    }
}

void kruskal(){
    init(n);
    while(!q.empty()&&tot!=cnt){
        node t=q.top();q.pop();
        int u=find(t.to);
        int v=find(t.from);
        if(u!=v){
            merge(u,v);
            ans+=t.cost;
            tot++;
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>h[i];
    }
    for(int i=1;i<=m;i++){
        int u,v,w;cin>>u>>v>>w;
        if(h[u]<h[v]) swap(u,v);
        G[u].push_back({v,w});
        if(h[u]==h[v]) G[v].push_back({u,w});
    }
    v[1]=true;build(1);kruskal();
    cout<<cnt+1<<" "<<ans<<'\n';
    return 0;
}