[SCOI2012] 滑雪

題目描述

a180285 非常喜歡滑雪。他來到一座雪山，這里分布著 \(m\) 條供滑行的軌道和 \(n\) 個軌道之間的交點（同時也是景點），而且每個景點都有一編號 \(i\space (1 \le i \le n)\) 和一高度 \(h_i\)。

a180285 能從景點 \(i\) 滑到景點 \(j\) 當(dāng)且僅當(dāng)存在一條 \(i\) 和 \(j\) 之間的邊，且 \(i\) 的高度不小于 \(j\)。與其他滑雪愛好者不同，a180285 喜歡用最短的滑行路徑去訪問盡量多的景點。如果僅僅訪問一條路徑上的景點，他會覺得數(shù)量太少。

于是 a18028 5拿出了他隨身攜帶的時間膠囊。這是一種很神奇的藥物，吃下之后可以立即回到上個經(jīng)過的景點（不用移動也不被認(rèn)為是 a180285 滑行的距離）。

請注意，這種神奇的藥物是可以連續(xù)食用的，即能夠回到較長時間之前到過的景點（比如上上個經(jīng)過的景點和上上上個經(jīng)過的景點）。 現(xiàn)在，a180285站在 \(1\) 號景點望著山下的目標(biāo)，心潮澎湃。他十分想知道在不考慮時間膠囊消耗的情況下，以最短滑行距離滑到盡量多的景點的方案（即滿足經(jīng)過景點數(shù)最大的前提下使得滑行總距離最小）。你能幫他求出最短距離和景點數(shù)嗎？

輸入格式

輸入的第一行是兩個整數(shù) \(n,m\)。
接下來一行有 \(n\) 個整數(shù) \(h_i\)，分別表示每個景點的高度。

接下來 \(m\) 行，表示各個景點之間軌道分布的情況。每行三個整數(shù) \(u,v,k\)，表示編號為 \(u\) 的景點和編號為 \(v\) 的景點之間有一條長度為 \(k\) 的軌道。

輸出格式

輸出一行，表示 a180285 最多能到達(dá)多少個景點，以及此時最短的滑行距離總和。

樣例 #1

樣例輸入 #1

3 3 
3 2 1 
1 2 1 
2 3 1 
1 3 10

樣例輸出 #1

3 2

提示

【數(shù)據(jù)范圍】
對于 $ 30% $ 的數(shù)據(jù)，$ 1 \le n \le 2000 $；
對于 $ 100% $ 的數(shù)據(jù)，$ 1 \le n \le 10^5 $。

對于所有的數(shù)據(jù)，保證 $ 1 \le m \le 10^6 $ , $ 1 \le h_i \le 10^9 $ ，$ 1 \le k_i \le 10^9 $。

分析

先從1號點出發(fā)搜索所有能遍歷的點，順便記下遍歷過的邊。

以終點的高度為第一關(guān)鍵字從大到小，以邊的長度為第二關(guān)鍵字從小到大，對標(biāo)記的邊排序。

前者保證能遍歷盡可能多的點，后者保證最小距離。

合并邊到新的生成樹上即可。

注意同樣高度的點建雙向邊。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+100,M=1e6+100;
struct edge{int y,n,x;long long z;}e[M<<1],t[M<<1];
int n,m,h[N],f[N];
int tot,cnt,head[N],sum;
int dh[N],rec[N],q[M];
bool vis[N];
long long dis;
bool cmp(edge a,edge b)
{
    if(h[a.y]==h[b.y])return a.z<b.z;
    return h[a.y]>h[b.y];
}
int fin(int x)
{
    if(f[x]==x)return x;
    f[x]=fin(f[x]);
    return f[x];
}
void bfs()
{
    int he=1,ta=0;
    q[++ta]=1;sum=1;vis[1]=1;
    while(he<=ta)
    {
        int u=q[he];
        ++he;
        for(int i=head[u];i;i=e[i].n)
        {
            int v=e[i].y;
            t[++cnt].n=dh[u];
            t[cnt].y=v;
            t[cnt].z=e[i].z;
            t[cnt].x=u;
            dh[u]=cnt;
            if(!vis[v])
            {
                vis[v]=1;
                ++sum;
                q[++ta]=v;
            }
        }
    }
}
void go(int u,int fa,long long len)
{
    bool fl=0;
    for(int i=dh[u];i;i=t[i].n)
    {
        int v=t[i].y;
        if(v==fa)continue;
        go(v,u,len+t[i].z);
        fl=1;
    }
    if(!fl)dis+=len;
}
int main()
{
    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;++i){f[i]=i;scanf("%d",h+i);}
    for(int i=1,x,y;i<=m;++i)
    {
        long long z=0;
        scanf("%d%d%lld",&x,&y,&z);
        if(h[x]<h[y])swap(x,y);// x --> y
        e[++tot].n=head[x];
        e[tot].x=x;
        e[tot].y=y;
        e[tot].z=z;
        head[x]=tot;
        if(h[x]==h[y])
        {
            e[++tot].n=head[y];
            e[tot].x=y;
            e[tot].y=x;
            e[tot].z=z;
            head[y]=tot;
        }
    }
    bfs();
    sort(t+1,t+1+cnt,cmp);
    int num=0;
    for(int i=1,x,y,fx,fy;i<=cnt;++i)
    {
        x=t[i].x;
        y=t[i].y;
        fx=fin(x);
        fy=fin(y);
        if(fx!=fy)
        {
            f[fy]=fx;
            dis+=t[i].z;
            ++num;
            if(num==sum-1)break;
        }
    }
    printf("%d %lld",sum,dis);

    return 0;
}