题解 P2483 【【模板】k短路 / [SDOI2010]魔法猪学院】

kekeke · 2020-02-27 18:01:27 · 题解

题意分析：

​ 本题求的是在路径权值之和不超过 E 的前提下，选择最多的不同路径，求可选择的最多的路径数。很明显，根据贪心思想，我们肯定要是求路径权值排名为第 k 短的路径。

算法分析：

​ 对于最短路，我们是可以轻松搞定的。因此我们考虑对最短路径进行修改，以此得到前 k 短路。我们考虑在反图 R 上以节点 n 为根节点，建立最短路树。最短路树就是以最短路上的边构成的图。对于一个点 x ，它可能会有多条最短路，我们只需要保留一条最短路就行。因此这样建出来的最短路树一定是一棵树。至于建最短路树，只需在反图 R 上使用 Dijkstra 等单源最短路算法解决即可（你要用 SPFA 我也不拦你）。

​ 建出最短路树后，我们定义最短路树上的边为树边，非最短路树上的边为非树边。此时，对于一条路径，它一定是由若干条树边和非树边组成，我们可以使用由非树边组成的序列来表示。假如当前已经得到了一条路径的非树边序列，我们考虑如何如何对其进行修改，使其产生新的非树边序列。很明显，我们有两种方法：替换一条非树边，或新添一条非树边。我们只考虑在非树边序列末尾进行修改和新添。

​ 我们先定义一些量：

​ dis_i ：点 i 到点 n 的最短路权值之和。

​ e.u,e.v,e.w ：非树边 e 的起点，终点和权值。

​ \Delta e ：将非树边 e 加入非树边序列所增加的权值。很明显，\Delta e=e.w+dis_{e.v}-dis_{e.u} 。

​ 首先考虑新添一条非树边。此时有哪些非树边可以加入呢？因为我们可以在树边上走一段距离后再走其他的非树边，所以我们需要从以最后一条非树边所指向的点以及这个点在最短路树上的祖先为起点的非树边中进行选择。

​ 再考虑替换一条非树边。此时我们可以从以该非树边的起始点以及它在最短路树上的祖先为起点的非树边中进行选择替换。

​ 那么我们可以得出一个寻找k短路的算法：我们采用类似于 Dijkstra 的贪心思路，用一个堆维护当前所有的非树边序列中权值最小的非树边序列（ \Sigma e 最小），同时我们还要记录这个序列中最后一条非树边的编号（在下文中的堆中的节点编号）。我们每次选取当前权值最小的路径统计答案，并使用这条路径拓展出新的路径。为了不遗漏地找出每条路径，我们对最后一条非树边进行替换时，要选择权值不小于当前非树边的权值最大的符合条件的非树边进行替换，然后再将新产生的非树边序列的 \Sigma e 以及最后一条边的编号（同上文）放入堆中；在新添非树边时，也要从当前权值最小的符合条件的非树边中选取出一条边进行拓展，再将新产生的非树边序列的相关信息（同替换）放入堆中。对于寻找以一个节点以及其最短路树上的祖先为起点的非树边，我们考虑以每条非树边的 \Delta e 为关键字，每个节点都用一个堆维护这些信息。因为父节点和子节点之间的包含关系，我们选择用可持久化左偏树进行维护。详细注释见代码。

注意：

​ 由于到达点 n 就必须立即结束，所以我们需要把所有以 n 为起点的边去掉。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>

#define ll long long

using namespace std;

inline int read()
{
    int s=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
    return s*f;
}

const int N=5e4+5,M=2e5+3;

struct edge{int net,to;double w;};
struct Graph
{
    int tot,head[N];edge Edge[M];
    void add(int x,int y,double z){Edge[++tot]=(edge){head[x],y,z};head[x]=tot;}
}G,R;

int n,m,ans=0;double E;

struct node
{
    int id;double dis;
    friend bool operator<(node x,node y){return x.dis>y.dis;}
};
int vis[N],fa[N];double dis[N];
void dijkstra()//求其他点到达n的最短路，并建立最短路树 
{
    priority_queue<node>q;q.push((node){n,0});
    memset(dis,127,sizeof(dis));dis[n]=0;
    while(!q.empty())
    {
        node u=q.top();q.pop();
        if(vis[u.id])continue;
        vis[u.id]=1;
        for(int i=R.head[u.id];i;i=R.Edge[i].net)
        {
            node v=(node){R.Edge[i].to,u.dis+R.Edge[i].w};
            if(dis[v.id]>v.dis)
            {
                dis[v.id]=v.dis;
                fa[v.id]=i;//记录最短路树上指向点v.id的边的编号 
                q.push(v);
            }
        }
    }
}

int seq[N],rt[N];
bool cmp(const int x,const int y){return dis[x]<dis[y];}

//可持久化左偏树 
struct heap{int l,r,dist,fa;double key;}tree[21*N];
int cnt=0;
int make_new(int f,double val)
{
    int k=++cnt;
    tree[k].l=tree[k].r=tree[k].dist=0;
    tree[k].fa=f;tree[k].key=val;
    return k;
}
int merge(int x,int y)
{
    if(!x||!y)return x+y;
    if(tree[x].key-tree[y].key>0)swap(x,y);
    int k=++cnt;
    tree[k]=tree[x];
    tree[k].r=merge(tree[k].r,y);
    if(tree[tree[k].l].dist<tree[tree[k].r].dist)swap(tree[k].l,tree[k].r);
    tree[k].dist=tree[tree[k].r].dist+1;
    return k;
}

struct ing
{
    int x;double ans;
    friend bool operator<(ing x,ing y){return x.ans>y.ans;}
};

int main()
{
    n=read();m=read();scanf("%lf",&E);
    for(int i=1;i<=m;i++)
    {
        int x=read(),y=read();double z;scanf("%lf",&z);
        if(x==n){i--;m--;continue;}//去掉以n为起点的边 
        G.add(x,y,z);R.add(y,x,z);
    }

    dijkstra();

    for(int i=1;i<=n;i++)seq[i]=i;
    sort(seq+1,seq+1+n,cmp);

    //建立可持久化左偏树来维护与每个点及其最短路树上的祖先相连的非树边 
    tree[0].dist=-1;
    for(int i=1;i<=n;i++)
    {
        int u=seq[i];
        for(int j=G.head[u];j;j=G.Edge[j].net)
        if(fa[u]!=j)rt[u]=merge(rt[u],make_new(G.Edge[j].to,G.Edge[j].w+dis[G.Edge[j].to]-dis[u]));
        rt[u]=merge(rt[u],rt[G.Edge[fa[u]].to]);
    }

    priority_queue<ing>q;
    if(E-dis[1]<0){printf("0\n");return 0;}
    E-=dis[1];ans++;
    if(rt[1])q.push((ing){rt[1],tree[rt[1]].key});
    while(!q.empty())
    {
        ing u=q.top();q.pop();
        if(E-(u.ans+dis[1])<0)break;
        E-=u.ans+dis[1];ans++;
        if(tree[u.x].l)q.push((ing){tree[u.x].l,u.ans-tree[u.x].key+tree[tree[u.x].l].key});
        if(tree[u.x].r)q.push((ing){tree[u.x].r,u.ans-tree[u.x].key+tree[tree[u.x].r].key});
        //对最后一条非树边进行替换 
        if(rt[tree[u.x].fa])q.push((ing){rt[tree[u.x].fa],u.ans+tree[rt[tree[u.x].fa]].key});
        //新添一条非树边 
    }

    printf("%d\n",ans);

    return 0;

}

参考博客：

​ https://www.mina.moe/archives/2777