Prim 40pts 求助
查看原帖
Prim 40pts 求助
547908
NightTide楼主2022/10/3 10:16

RT,后面两个点都过了,前面三个反而没过,求各位帮忙看看。

#include<bits/stdc++.h>
#define MAXN 100010
#define MAXM 1000010
using namespace std;
typedef long long ll;
struct edge{ int pre, to; ll w; };
struct node{ int high; ll dis; int id; };
bool operator < (node a, node b){
    if(a.high == b.high) return a.dis > b.dis;
    return a.high < b.high;
}
bool operator > (node a, node b){
    if(a.high == b.high) return a.dis < b.dis;
    return a.high > b.high;
}
edge e[MAXM];
int n, m, cnt; ll tot, ans;
int h[MAXN], head[MAXN];
ll dis[MAXN];
bool vis[MAXN];
void add_edge(int u, int v, int w){
    e[++cnt].pre = head[u];
    e[cnt].to = v; e[cnt].w = w;
    head[u] = cnt;
}
void prim(int st){
    memset(dis, 0x3f, sizeof(dis));
    priority_queue<node> q;
    dis[st] = 0; q.push((node){h[st], 0, st});
    while(!q.empty()){
        int now = q.top().id; q.pop();
        if(vis[now]) continue;
        vis[now] = true;
        tot++; ans += dis[now];
        for(int i = head[now]; i; i = e[i].pre){
            if(vis[e[i].to]) continue;
            if(dis[e[i].to] > e[i].w){
                dis[e[i].to] = e[i].w;
                q.push((node){h[e[i].to], dis[e[i].to], e[i].to});
            }
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; i++) scanf("%d",&h[i]);
    for(int i = 1; i <= m; i++){
        int u, v; ll w; scanf("%d%d%lld",&u,&v,&w);
        if(h[u] >= h[v]) add_edge(u, v, w);
        if(h[v] >= h[u]) add_edge(v, u, w);
    }
    prim(1);
    printf("%lld %lld\n",tot,ans);
    return 0;
}
2022/10/3 10:16
加载中...