「Solution」SCOI 滑雪与时间胶囊

SCOI 滑雪与时间胶囊

题目描述

a180285 非常喜欢滑雪。
他来到一座雪山，这里分布着$M$条供滑行的轨道和$N$个轨道之间的交点（同时也是景点），而且每个景点都有一编号$i(1<=i<=n)$和一高度$$。a180285 能从景点$i$滑到景点$j$当且仅当存在一条$i$和$j$之间的边，且$i$的高度不小于$j$。 与其他滑雪爱好者不同， a180285 喜欢用最短的滑行路径去访问尽量多的景点。如果仅仅访问一条路径上的景点，他会觉得数量太少。于是 a180285 拿出了他随身携带的时间胶囊。这是一种很神奇的药物，吃下之后可以立即回到上个经过的景点（不用移动也不被认为是 a180285 滑行的距离）。请注意，这种神奇的药物是可以连续食用的，即能够回到较长时间之前到过的景点（比如上上个经过的景点和上上上个经过的景点）。 现在， a180285 站在$1$号景点望着山下的目标，心潮澎湃。他十分想知道在不考虑时间胶囊消耗的情况下，以最短滑行距离滑到尽量多的景点的方案（即满足经过景点数最大的前提下使得滑行总距离最小）。你能帮他求出最短距离和景点数吗？ #### 输入格式 输入的第一行是两个整数$N$,$M$。 接下来$1$行有$N$个整数$H_i$，分别表示每个景点的高度。 接下来$M$行，表示各个景点之间轨道分布的情况。每行$3$个整数,$U_i$,$V_i$,$K_i$。表示编号为$U_i$的景点和编号为$V_i$的景点之间有一条长度为$K_i$的轨道。 #### 输出格式 输出一行，表示 a180285 最多能到达多少个景点，以及此时最短的滑行距离总和。 ##### 样例 ###### 样例输入 3 3 3 2 1 1 2 1 2 3 1 1 3 10 ###### 样例输出 3 2 ## 思路 用$Kruskal$或$Prim$肯定是过不了的,因为题目中有限制. 首先在输入时处理起点与终点,从高向低去存边,再用$DFS$从点$1$开始跑一遍,用$vis$存一下哪些边可以到达,最后用$node$存可以使用的边. 写一个$cmp$,以$u$的高度为第一关键字,用$w$为第二关键字. 最后跑一遍$Kruskal$或者$Prim$就可以求解.

#include <queue>
#include <vector>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 1e6 + 5;
const int MAXM = 5 * 1e6 + 5;

int n, m, h[MAXN], maxl, tot, cnt, fa[MAXN];
long long ans;
bool vis[MAXN];

struct node {
    int u, v, w;
} dis[MAXM];
bool cmp(node x, node y) {
    if (h[x.v] != h[y.v])
        return h[x.v] > h[y.v];
    else
        return x.w < y.w;
}

struct edge {
    int v, w;
    edge() {}
    edge(int V, int W) {
        v = V;
        w = W;
    }
};

vector<edge> G[MAXN];

void AddEdge(int u, int v, int w) { G[u].push_back(edge(v, w)); }

int FindSet(int v) {
    if (fa[v] == v)
        return fa[v];
    else
        return fa[v] = FindSet(fa[v]);
}
bool UnionSet(int u, int v) {
    int x = FindSet(u);
    int y = FindSet(v);
    if (x == y)
        return 0;
    else {
        fa[x] = fa[y];
        return 1;
    }
}
void Kruskal() {
    for (int i = 1; i <= n; i++) fa[i] = i;
    sort(dis + 1, dis + 1 + cnt, cmp);
    for (int i = 1; i <= cnt; i++) {
        if (UnionSet(dis[i].u, dis[i].v)) {
            ans += dis[i].w;
            tot++;
        }
        if (tot == maxl - 1)
            break;
    }
    printf("%lld\n", ans);
}

void dfs(int x) {
    vis[x] = 1;
    maxl++;
    for (int i = 0; i < G[x].size(); i++) {
        int v = G[x][i].v;
        if (!vis[v]) {
            dfs(v);
        }
    }
}

void intn() {
	for (int i = 1; i <= n; i++) {
		if (vis[i] == 1) {
			for (int j = 0; j < G[i].size(); j++) {
				if (vis[G[i][j].v] == 1) {
					cnt ++;
					dis[cnt].u = i;
					dis[cnt].v = G[i][j].v;
					dis[cnt].w = G[i][j].w;
				}
			}
		}
	}
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &h[i]);
    }
    for (int i = 1, ui, vi, wi; i <= m; i++) {
        scanf("%d %d %d", &ui, &vi, &wi);
        if (h[ui] >= h[vi]) {
            AddEdge(ui, vi, wi);
        }
        if (h[ui] <= h[vi]) {
            AddEdge(vi, ui, wi);
        }
    }
    dfs(1);
    printf("%d ", maxl);
    intn();
    Kruskal();
    return 0;
}