[BZOJ2753/Luogu2573][SCOI2012]滑雪与时间胶囊(生成树)

发布于 2018-02-21  99 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ2753/Luogu2573][SCOI2012]滑雪与时间胶囊(生成树)

Description

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

Http

BZOJ
Luogu

Tag

生成树

题目大意

给定一个有特殊性质的有向图,求最小树形图。

解决思路

直接把求最小树形图的朱刘算法拿过来是不行的,时间复杂度太高。
注意到这一道题中有向图的特殊性质,边总是从高的向低的走的,可以想象是按高度从高到低分成若干段来考虑。这个对于贪心很有帮助。
首先考虑为什么无向图的最小生成树算法不能直接照搬到有向图中。以\(Prim\)为例,无向图的生成树算法基于贪心原理,即若选当前距离最短的点进来不会差。但这个贪心在有向图中是不成立的,因为边有向。
放到这个题,由于边总是从高的连向低的,那么先考虑高的点不会更差,因为海拔更低的点不会更新高的点,所以我们可以类似从高到低地来考虑。又因为海拔相同的点,边相当于是无向的。所以就可以直接用无向图的最小生成树来解。
这里选择用\(Prim\)算法实现最小生成树,那么与常规的算法不一样的是,这里的比较就要优先比较海拔,再比较距离,这样才能满足上面的贪心。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=100100;
const int maxM=1000100*2;
const int inf=2147483647;

class Queue_Data
{
public:
    int u;
    ll dis;
};

ll Height[maxN];

bool operator < (Queue_Data A,Queue_Data B){//定义比较函数,注意先比较海拔
    if (Height[A.u]!=Height[B.u]) return Height[A.u]<Height[B.u];
    else return A.dis>B.dis;
}

int n,m;
int edgecnt=0,Head[maxN],Next[maxM],V[maxM];
ll W[maxM];
ll Dis[maxN];
bool vis[maxN];
priority_queue<Queue_Data> Q;

void Add_Edge(int u,int v,int w);

int main()
{
    mem(Head,-1);
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for (int i=1;i<=n;i++) cin>>Height[i];
    for (int i=1;i<=m;i++)
    {
        int u,v,w;cin>>u>>v>>w;//从高海拔向低海拔连比
        if (Height[u]>=Height[v]) Add_Edge(u,v,w);
        if (Height[v]>=Height[u]) Add_Edge(v,u,w);
    }
    mem(Dis,-1);Dis[1]=0;
    Q.push((Queue_Data){1,0});
    ll Ans=0,Sum=0;
    do//堆优化求解最小生成树
    {
        Queue_Data u=Q.top();Q.pop();
        if (vis[u.u]) continue;
        vis[u.u]=1;
        Ans++;Sum=Sum+(ll)Dis[u.u];
        for (int i=Head[u.u];i!=-1;i=Next[i])
            if ((vis[V[i]]==0)&&((Dis[V[i]]==-1)||(Dis[V[i]]>W[i]))){
                Dis[V[i]]=W[i];Q.push((Queue_Data){V[i],Dis[V[i]]});
            }
    }
    while (!Q.empty());
    printf("%lld %lld\n",Ans,Sum);
    return 0;
}

void Add_Edge(int u,int v,int w)
{
    edgecnt++;Next[edgecnt]=Head[u];Head[u]=edgecnt;V[edgecnt]=v;W[edgecnt]=w;
    return;
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ2753/Luogu2573][SCOI2012]滑雪与时间胶囊(生成树)


HNCJ OIer