BZOJ2753【SCOI2012】滑雪与时间胶囊 < MST >

Posted on Symbols count in article: 1.2k Reading time ≈ 4 mins.

Problem

【SCOI2012】滑雪与时间胶囊

Time  Limit:  50  Sec\mathrm{Time\;Limit:\;50\;Sec}
Memory  Limit:  128  MB\mathrm{Memory\;Limit:\;128\;MB}

Description

a180285\mathrm{a180285}非常喜欢滑雪。他来到一座雪山，这里分布着MM条供滑行的轨道和NN个轨道之间的交点（同时也是景点），而且每个景点都有一编号ii（1≤i≤N1\le i\le N）和一高度HiH_i。a180285\mathrm{a180285}能从景点ii滑到景点jj当且仅当存在一条ii和jj之间的边，且ii的高度不小于jj。 与其他滑雪爱好者不同，a180285\mathrm{a180285}喜欢用最短的滑行路径去访问尽量多的景点。如果仅仅访问一条路径上的景点，他会觉得数量太少。于是a180285\mathrm{a180285}拿出了他随身携带的时间胶囊。这是一种很神奇的药物，吃下之后可以立即回到上个经过的景点（不用移动也不被认为是a180285\mathrm{a180285}滑行的距离）。请注意，这种神奇的药物是可以连续食用的，即能够回到较长时间之前到过的景点（比如上上个经过的景点和上上上个经过的景点）。 现在，a180285\mathrm{a180285}站在11号景点望着山下的目标，心潮澎湃。他十分想知道在不考虑时间胶囊消耗的情况下，以最短滑行距离滑到尽量多的景点的方案（即满足经过景点数最大的前提下使得滑行总距离最小）。你能帮他求出最短距离和景点数吗？

Input

输入的第一行是两个整数NN，MM。
接下来11行有NN个整数HiH_i，分别表示每个景点的高度。
接下来MM行，表示各个景点之间轨道分布的情况。每行33个整数，Ui,Vi,KiU_i,V_i,K_i。表示
编号为UiU_i的景点和编号为ViV_i的景点之间有一条长度为KiK_i的轨道。

Output

输出一行，表示a180285\mathrm{a180285}最多能到达多少个景点，以及此时最短的滑行距离总和。

Sample Input

1
2
3
4
5
3 3
3 2 1
1 2 1
2 3 1
1 3 10

Sample Output

1
3 2

HINT

对于30%30\%的数据，保证1≤N≤20001\le N\le 2000
对于100%100\%的数据，保证1≤N≤1051\le N\le10^5, 1≤M≤1061\le M\le10^6, 1≤Hi≤1091\le H_i\le10^9, 1≤Ki≤1091\le K_i\le10^9。

标签：MST

Solution

原题的一大坨叙述就是求有向图中从一点出发能达到的点数和最小生成树边权和。

第一问直接BFS\mathrm{BFS}出解。
第二问比较麻烦，还是做Kruskal\mathrm{Kruskal}，只是排序的时候以终点高度从高到低为第一关键字，以边权从低到高为第二关键字。

原理：
首先，同一高度的点间一定是双向边，于是是一个强连通分量，如果把每个高度的点缩起来，那么最后一定会形成一个DAG\mathrm{DAG}，从11开始沿拓扑序遍历每个强连通分量，这个强连通分量中的边都是双向边，可以在这个强连通分量中跑Kruskal\mathrm{Kruskal}，除了这些边以外还可能有从上面的点连下来的点。因此如果按终点高度为第一关键字排序，那么到一个高度时一定是此高度强连通分量内部的双向边和前面连到此强连通分量的边，符合Kruskal\mathrm{Kruskal}贪心的前提。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
#define MAX_N 100000
#define MAX_M 2000000
#define pb push_back
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, p, h[MAX_N+5], fa[MAX_N+5];
vector <int> G[MAX_N+5]; bool mrk[MAX_N+5];
struct node {int u, v, w; lnt c;} E[MAX_M+5];
bool cmp (const node &a, const node &b) {
    return a.w == b.w ? a.c < b.c : a.w > b.w;
}
int getf(int x) {return fa[x] == x ? x : fa[x] = getf(fa[x]);}
int BFS() {
    int ret = 1;	mrk[1] = true;
    queue <int> que; que.push(1);
    while (!que.empty()) {
        int u = que.front(); que.pop();
        for (int i = 0, v; i < (int)G[u].size(); i++)
            if (!mrk[v = G[u][i]]) que.push(v), mrk[v] = true, ret++;
    }
    return ret;
}
int main() {
    read(n), read(m);	lnt ans = 0;
    for (int i = 1; i <= n; i++) fa[i] = i;
    for (int i = 1; i <= n; i++) read(h[i]);
    for (int i = 0; i < m; i++) {
        int u, v; lnt c; read(u), read(v), read(c);
        if (h[u] >= h[v]) G[u].pb(v), E[++p] = (node){u, v, h[v], c};
        if (h[u] <= h[v]) G[v].pb(u), E[++p] = (node){v, u, h[u], c};
    }
    sort(E+1, E+(m=p)+1, cmp), printf("%d ", BFS());
    for (int i = 1, u, v; i <= m; i++)
        if (mrk[E[i].u] && mrk[E[i].v]) {
            u = getf(E[i].u), v = getf(E[i].v);
            if (u^v) fa[u] = v, ans += E[i].c;
        }
    return printf("%lld\n", ans), 0;
}