[SCOI2012]滑雪与时间胶囊

BZOJ2753
有点意思的题..
算法是按到达点高度为第一关键字,边权为第二关键字排序,然后搞最小生成树
按到达点高度为第一关键字,保证了它跑出来是个树形图
在此基础上按边权为第二关键字排序,保证了权值最小
 
代码如下:

#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;

}