7.3 滑雪与时间胶囊

题目链接

滑雪与时间胶囊

题目思路

要先用dfs把从1能到的点筛选出来, 加边的时候不要else if 因为当H[a] == H[b]的时候, 是双向边
然后用Kruskal算法求解

代码实现

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 1e6 + 10, M = 3e6 + 10;

int e[M], ne[M], h[N], idx;
int p[N], H[N];
int n, m; 
LL cnt, res;
bool vis[N];

struct Edge
{
    int u, v, w;
    bool operator < (const Edge &W)const
    {
        if (H[v] != H[W.v]) return H[v] > H[W.v];
        return w < W.w;
    }
}edge[M];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int find(int a)
{
    if (p[a] != a) p[a] = find(p[a]);
    return p[a];
}

void dfs(int nu)
{
    vis[nu] = 1;
    cnt ++;
    for (int i = h[nu]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (vis[j]) continue;
        dfs(j);
    }
}

void Kruskal()
{
    sort(edge, edge + m);

    for (int i = 1; i <= n; i ++ ) p[i] = i;

    for (int i = 0; i < m; i ++ )
    {
        auto e = edge[i];

        if (!vis[e.u] || !vis[e.v]) continue;

        int pu = find(e.u), pv = find(e.v);

        if (pu != pv)
        {
            p[pu] = pv;
            res += (LL)e.w;
        }
    }
}

int main()
{
    cin.tie(0); cout.tie(0);
    ios::sync_with_stdio(false);

    memset(h, -1, sizeof h);

    cin >> n >> m;

    for (int i = 1; i <= n; i ++ ) cin >> H[i];

    for (int i = 0; i < m; i ++ )
    {
        int a, b, c;
        cin >> a >> b >> c;
        if (H[a] >= H[b]) edge[i] = {a, b, c}, add(a, b);
        if (H[a] <= H[b]) edge[i] = {b, a, c}, add(b, a);
    }

    dfs(1);

    Kruskal();

    cout << cnt << ' ' << res << endl;

    return 0;
}