[SCOI2012]滑雪与时间胶囊

#include <stdio.h>
#include <string.h>
#include <map>
#include <algorithm>
 
#ifdef WiN32
#define lld "%I64d"
#else
#define lld "%lld"
#endif
 
const int N = 100000;
const int M = 2000000;
 
typedef long long Long;
 
struct node
{
    int first;
};
 
int hei[N + 10];
 
struct road
{
    int f;
    int t;
    int w;
    int next;
     
    bool operator < (const road & b)const
    {
        if(hei[t] == hei[b.t])
            return w < b.w;
        return hei[t] > hei[b.t];
    }
};
 
node nodes[N + 10];
road roads[2 * M + 10];
 
int st[N + 10];
std::map<int,int> map;
 
int min[N + 10];
 
int tot = 0;
void add(int f,int t,int w)
{
    tot ++;
    roads[tot].f = f;
    roads[tot].t = t;
    roads[tot].w = w;
    roads[tot].next = nodes[f].first;
    nodes[f].first = tot;
}
 
int vis[N + 10];
int queue[N + 10];
void BFS(int s)
{
    int head = 0;
    int tail = 0;
    queue[tail++] = s;
     
    int now_f = 0;
    int now_s = 0;
    do
    {
        now_f = queue[head++];
        vis[now_f] = true;
        for(int r = nodes[now_f].first;r;r = roads[r].next)
        {
            now_s = roads[r].t;
            if(vis[now_s])
                continue;
            vis[now_s] = true;
            queue[tail++] = now_s;
        }
    }
    while(head != tail);
}
 
int f[N + 10];
 
int find(int a)
{
    if(f[a] == a)
        return a;
    return f[a] = find(f[a]);
}
 
const int INF = 1000000001;
 
int main()
{
    for(int i = 1;i <= N;i++)
    {
        f[i] = i;
        min[i] = INF;
    }
     
    int n = 0;
    int m = 0;
    scanf("%d%d",&n,&m);
     
    for(int i = 1;i <= n;i++)
    {
        scanf("%d",hei + i);
        st[i] = hei[i];
    }
    /*
    std::sort(st + 1,st + 1 + n);
     
    for(int i = 1;i <= n;i++)
        map[st[i]] = i;
     
    for(int i = 1;i <= n;i++)
        hei[i] = map[hei[i]];
    */
    int u = 0;
    int v = 0;
    int d = 0;
    for(int i = 1;i <= m;i++)
    {
        scanf("%d%d%d",&u,&v,&d);
         
        if(hei[u] == hei[v])
        {
            add(u,v,d);
            add(v,u,d);
            continue;
        }
         
        if(hei[u] > hei[v])
            add(u,v,d);
        else add(v,u,d);
    }
     
    BFS(1);
     
    std::sort(roads + 1,roads + 1 + tot);
     
    Long res2 = 0;
     
    for(int i = 1;i <= tot;i++)
    {
        if((!vis[roads[i].f]) || (!vis[roads[i].t]))
            continue;
        /*
        if(hei[roads[i].f] != hei[roads[i].t])
        {
            if(roads[i].w < min[hei[roads[i].t]])
            {
                min[hei[roads[i].t]] = roads[i].w;
            }
        }
        else*/
        {
            if(find(roads[i].f) != find(roads[i].t))
            {
                f[find(roads[i].f)] = find(roads[i].t);
                res2 += roads[i].w;
            }
        }
    }
     
    int res1 = 0;
    for(int i = 1;i <= N;i++)
    {
        res1 += (int)vis[i];
        res2 += (Long)(min[i] < INF) * min[i];
    }
     
    printf("%d "lld"\n",res1,res2);
     
    return 0;
}