P2573 [SCOI2012] 滑雪

原题链接

题解

这题乍一看好像是一道最小生成树的模板题，但如果直接找模板打会发现WA。

仔细一看这题是有向图的最小生成树，可以直接套朱刘算法，but，我还不会······

直接套模板的反例

3
3 2 1
1 2 5
1 3 2
2 3 1

所以我们再分析题目，发现只要把山的高度设为第一优先级，边的权值为第二优先级，再建树即可。

code

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int M=2e6+5;
typedef long long ll;
int head[N],Next[M],to[M],h[N],weight[M];
bool vis[N];
int n,m,cnt=1,sum=0;
ll pre=0;
struct node{
    int id,value;
    bool operator <(const node &a)const{
        if (h[id]!=h[a.id]) return h[id]<h[a.id];
        return value>a.value;
    }
};
void build(int from,int to_,int w){
    Next[cnt]=head[from];
    to[cnt]=to_;
    weight[cnt]=w;
    head[from]=cnt++;
}
void prim(int from){
    priority_queue<node> que;
    node x;
    x.id=from;
    x.value=0;
    que.push(x);
    while (!que.empty()){
        x=que.top();
        que.pop();
        if (vis[x.id]) continue;
        else vis[x.id]=true;
        sum++;
        pre+=x.value;
        for (int i=head[x.id];i>0;i=Next[i]){
            node y;
            y.id=to[i];
            y.value=weight[i];
            que.push(y);
        }
    }
}
int main(){
    cin>>n>>m;
    for (int i=1;i<=n;i++){
        cin>>h[i];
    }
    for (int i=1;i<=m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        if (h[a]>=h[b]) build(a,b,c);
        if (h[a]<=h[b]) build(b,a,c);
    }
    prim(1);
    cout<<sum<<" "<<pre;
    return 0;
}