【每日一题】滑雪与时间胶囊

[SCOI2012]滑雪与时间胶囊

http://www.nowcoder.com/questionTerminal/b21e6e9227974d3888cb4a3912f59a59

题意:

有n个点,然后有m条边,且你只能从权值高的点走到权值低的点;且你可以回到之前你曾经走过的点,然后问从1出发,最多可以遍历多少个点,且遍历最多点时最小距离是多少?

思路:

首先需要保证遍历的点最多,应该希望新加入的点高度越高越好,因为这样就不会漏掉一些本来可以遍历的点,然后再希望距离越小越好;做一遍prim,将点加入生成树时以高度降序,到生成树距离升序来取,且每到一个点的代价就是这个点到生成树中所有点集中的最短路

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
const int N = 1e5+10,M = 2e6+10;
struct Edge{
    int to,w,nex;
}e[M];
int dist[N],H[N];
struct Node{
    int high,dist,id;
    bool operator < (const Node&b) const{
        if(high != b.high) return high < b.high;
        return dist > b.dist;
    }
};
int head[N],idx;
void add_edge(int u,int v,int w){
    e[idx].to = v;
    e[idx].w = w;
    e[idx].nex = head[u];
    head[u] = idx++;
}
void init(){
    memset(head,-1,sizeof(head));idx = 0;
} 
int n,m,cnt,intree[N];
ll ans;
void prim(){
    priority_queue<Node> q;
    memset(dist,0x3f,sizeof(dist));
    dist[1] = 0;
    q.push((Node){H[1],0,1});
    while(q.size()){
        int u = q.top().id;q.pop();
        if(intree[u]) continue;
        intree[u] = 1;cnt++,ans+=dist[u];
        for(int i = head[u];~i;i = e[i].nex){
            int v = e[i].to,w = e[i].w;
            if(intree[v]) continue;
            if(dist[v] > w){
                dist[v] = w;
                q.push((Node){H[v],dist[v],v});
            }
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i++) scanf("%d",H+i);
    init();
    for(int i = 0,u,v,w;i < m;i++){
        scanf("%d%d%d",&u,&v,&w);
        if(H[u] >= H[v]) add_edge(u,v,w);
        if(H[v] >= H[u]) add_edge(v,u,w);
    }
    prim();
    printf("%d %lld\n",cnt,ans);
    return 0;
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-16 14:00
白火同学:其实你可以了解一下HR在Boss聊天的机制,想赢牌的前提是先会玩牌。 如果HR长时间没有理你,有可能是因为你的消息被其他应聘者的消息给挤到下面了,HR从上到下有可能只看个三四百个人就要到理想数量的简历了,而你恰好没有被看到,时间一长,你的消息在越来越下面。这种情况就需要你自己活跃一下,把消息提上去。 也可能是HR招的合适的人选了,但会一直挂着岗位,为了省重新开招聘岗位的钱,方便后面随时修改招聘要求。 当然也可能是HR吃饱了没事耍你玩,要了你的简历又不看,就看你自己怎么理解了。
点赞 评论 收藏
分享
牛客刘北:如果暑期实习是27届的话,你要晚一年才会毕业,企业为什么会等你呢?要搞清时间逻辑呀!27届现在实习只能是在暑假实习,这是日常实习,不是暑期实习。所以多去投日常实习吧,暑期实习肯定不会要你的
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务