经典算法不用改一改, 就不会做了…

记得找每个变量间的联系来简化程序

懵逼的 题目

扯淡的 题解

我们发现…这个题…能到达的点一定形成了一棵树, 而且因为要”满足经过景点数最大的前提”, 所以这个图中所有从1能到达的点都要到达, 那么我们发现这就是有向图(这个图中的边是在以1为起点进行bfs的时候能经过的边)中一个固定起点的最小生成树

然而怎么求呢?

我: 直接当成无向图求

昊哥: 你sb吗, 然后丢出一张图

GG

我: …那你拓扑排序一遍, 然后先按照拓扑的编号排序分层, 然后再按照边权做最小生成树

昊哥: 你sb吗, 按照拓扑排序做出的编号不就是按照高度排序做出来的编号

我: …昊哥你收小弟嘛?

所以这个题目就是:

  • $bfs$, 找出能到达的节点, 这些节点就是你在滑雪的时候能到达的点, 记录每一条能到达的边
  • 把这些边按照终点的高度为第一关键字, 边权为第二关键字排序
  • 跑$kruskal$, $MST$的大小就是最终的花费

然后…$\downarrow:$我写的$kruskal$…然后我就重构了两遍, 调了一天… 艹

GG

沙茶的 代码

/**************************************************************
    Problem: 2753
    User: Cansult
    Language: C++
    Result: Accepted
    Time:15072 ms
    Memory:129192 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define MAXN (100000 + 5)
#define MAXM (1000000 + 5)
#define LL long long
#define int LL 
using namespace std;
struct edg
{
    int from, to, next, cost;
    edg() {}
    edg(int fr, int dqt, int nex, int dqc): from(fr), to(dqt), next(nex), cost(dqc) {}
}b[MAXM << 1], e[MAXM << 1];
int g[MAXN], cntb, n, m, na, me, he[MAXN], fa[MAXN], ans;
void adn(int from, int to, int cost)
{
    b[++cntb] = edg(from, to, g[from], cost);
    g[from] = cntb;
}
void bfs()
{
    bool vis[MAXN];
    queue<int> q;
    memset(vis, false, sizeof(vis));
    q.push(1), vis[1] = true;
    na = 1;
    while (!q.empty())
    {
        int dq = q.front();
        q.pop();
        for (int i = g[dq]; i; i = b[i].next)
        {
            e[++me] = b[i];
            if (!vis[b[i].to])
                vis[b[i].to] = true, ++na, q.push(b[i].to);
        }
    }
}
bool cmp(edg x, edg y)
{ return (he[x.to] > he[y.to] || (he[x.to] == he[y.to] && x.cost < y.cost)); }
int find(int x)
{ return (x == fa[x] ? x : (fa[x] = find(fa[x]))); }
void uni(int x, int y)
{ fa[find(x)] = find(y); }
void kruskal()
{
    for (int i = 1; i <= n; i++) fa[i] = i;
    sort(e + 1, e + me + 1, cmp);
    int cnte = 0;
    for (int i = 1; i <= me; i++)
        if (find(e[i].from) != find(e[i].to))
        {
            uni(e[i].from, e[i].to);
            ans += e[i].cost;
            ++cnte;
            if (cnte == na - 1)
                break;
        }
}
main()
{
    // freopen("in.in", "r", stdin);
    // freopen("wa.out", "w", stdout);
    scanf("%lld%lld", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &he[i]);
    for (int i = 1, srx, sry, srz; i <= m; i++)
    {
        scanf("%lld%lld%lld", &srx, &sry, &srz);
        if (he[srx] > he[sry])
            adn(srx, sry, srz);
        else if (he[srx] < he[sry])
            adn(sry, srx, srz);
        else
            adn(srx, sry, srz), adn(sry, srx, srz);
    }
    bfs();
    kruskal();
    printf("%lld %lld\n", na, ans);
    return 0;
}

By 昊哥的3001号小弟 Cansult