[学习笔记]k短路

ゝ一世哀愁。 2021-12-23 15:17 168阅读 0赞

A\*：我已经忘了怎么写了，反正n=30，m=1000都能卡掉。。。

正解：可持久化左偏树+堆维护可能集合

原论文：[http://www.docin.com/p-1387370338.html][http_www.docin.com_p-1387370338.html]

概括：

结论：

1.t为根求最短路树T，定义P'为路径s-t的路径P和T没有交集的部分，P’和P都是有序边集

对于P'中相邻边一定存在tail和head的祖先后代关系（或者重合）

2.新定义边的代价：dis\[v\]+w-dis\[u\]，即换边走的额外可能花费

这样一个P就是：dis\[1~n\]+∑e∈P' newweight\[e\]

3.P和P'一一对应。

求法：

1.T为根求最短路树

2.非树边放进u的左偏树内，

3.dfs可持久化合并堆，得到到根路径上的出边的堆

4.堆维护四元组(u,v,pos,val)边集倒数第二条边tail是u，倒数第一条边tail是v，v的这个边的左偏树节点编号pos，P’的代价val

更新：

A.v找到rt\[v\]最小的加入P的末尾

B.u找到rt\[u\]下一个最小的边作为新的v和pos，这个边一定是pos的左儿子或者右儿子

初始：(0,1,\*,0)要特判

注意特判：

A.rt\[v\]=0?

B.pos没有左右儿子？

#include<bits/stdc++.h>
    #define reg register int
    #define il inline
    #define fi first
    #define se second
    #define mk(a,b) make_pair(a,b)
    #define numb (ch^'0')
    #define pb push_back
    #define solid const auto &
    #define enter cout<<endl
    #define pii pair<int,int>
    using namespace std;
    typedef long long ll;
    template<class T>il void rd(T &x){
        char ch;x=0;bool fl=false;
        while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
        for(x=numb;isdigit(ch=getchar());x=x*10+numb);
        (fl==true)&&(x=-x);
    }
    template<class T>il void output(T x){
        if(x/10)output(x/10);putchar(x%10+'0');}
    template<class T>il void ot(T x){
        if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}
    template<class T>il void prt(T a[],int st,int nd){
        for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}
    
    namespace Miracle{
    const int N=5005;
    const int M=200000+5;
    int n,m;
    double E;
    struct node{
        int nxt,to;
        double val;
    }e[M];
    int hd[N],cnt=0;
    void add(int x,int y,double z){
        e[++cnt].nxt=hd[x];
        e[cnt].to=y;e[cnt].val=z;
        hd[x]=cnt;
    }
    
    struct edge{
        int x,y;
        double z;
    }b[M];
    double dis[N];
    struct po{
        int x;double val;
        po(){}
        po(int xx,double vv){
            x=xx;val=vv;
        }
        bool friend operator <(po a,po b){
            return a.val>b.val;
        }
    };
    priority_queue<po>q;
    bool vis[N];
    int pre[N];
    void dij(){
        memset(dis,127,sizeof dis);
        dis[n]=0;
        q.push(po(n,0));
        while(!q.empty()){
            po now=q.top();q.pop();
            if(vis[now.x]) continue;
            int x=now.x;
            vis[x]=1;
            for(reg i=hd[x];i;i=e[i].nxt){
                int y=e[i].to;
                if(dis[y]>dis[x]+e[i].val){
                    dis[y]=dis[x]+e[i].val;
                    pre[y]=i;
                    q.push(po(y,dis[y]));
                }
            }
        }
    }
    bool on[M];
    struct tr{
        int ls,rs;
        int d,id;
        double val;
        tr(){}
        tr(double v,int ddd){
            ls=0,rs=0;val=v;d=1;id=ddd;
        }   
    }t[M*20];
    int tot;
    int rt[N];
    int merge(int x,int y,int typ){
        if(!x||!y) return x+y;
        if(t[x].val>t[y].val) swap(x,y);
        if(typ){
            int nw=++tot;
            t[nw]=t[x];
            x=nw;
        }
        t[x].rs=merge(t[x].rs,y,typ);
        if(t[t[x].ls].d<t[t[x].rs].d) swap(t[x].ls,t[x].rs);
        t[x].d=t[t[x].rs].d+1;
        return x;
    }
    struct sol{
        int u,v,pos;
        double val;
        sol(){}
        sol(int uu,int vv,int pp,double vd){
            u=uu;v=vv;pos=pp;val=vd;
        }
        bool friend operator <(sol a,sol b){
            return a.val>b.val;
        }
    };
    void dfs(int x){
        for(reg i=hd[x];i;i=e[i].nxt){
            int y=e[i].to;
            rt[y]=merge(rt[y],rt[x],1);
            dfs(y);
        }
    }
    priority_queue<sol>hp;
    
    int main(){
        rd(n);rd(m);scanf("%lf",&E);
        for(reg i=1;i<=m;++i){
            rd(b[i].x);rd(b[i].y);scanf("%lf",&b[i].z);
            add(b[i].y,b[i].x,b[i].z);
        }
        dij();
        // for(reg i=1;i<=n;++i){
        //     cout<<i<<" : "<<dis[i]<<endl;
        // }
        memset(hd,0,sizeof hd);
        cnt=0;
        for(reg i=1;i<n;++i){
            on[pre[i]]=1;
            int id=pre[i];
            add(b[id].y,b[id].x,b[id].z);
        }
        for(reg i=1;i<=m;++i){
            if(!on[i]){
                t[++tot]=tr(dis[b[i].y]+b[i].z-dis[b[i].x],i);
                rt[b[i].x]=merge(rt[b[i].x],tot,0);
            }
        }
        dfs(n);
        hp.push(sol(0,1,-233,0));
        double st=dis[1];
        ll ans=0;
        while(!hp.empty()){
            sol now=hp.top();hp.pop();
            E-=now.val+st;
            if(E<0) break;
            ++ans;
            int u=now.u,v=now.v;
            if(now.v==1&&now.u==0){
                if(rt[1]){
                    sol lp=now;
                    lp.u=1;
                    lp.pos=rt[1];
                    lp.val=t[rt[1]].val;
                    lp.v=b[t[rt[1]].id].y;
                    hp.push(lp);
                }
            }else{
                if(rt[now.v]){
                    sol lp=now;
                    lp.u=v;
                    lp.pos=rt[lp.u];
                    lp.val+=t[rt[lp.u]].val;
                    lp.v=b[t[rt[lp.u]].id].y;
                    hp.push(lp);
                }
                if(t[now.pos].ls){
                    sol lp=now;
                    lp.pos=t[lp.pos].ls;
                    lp.val+=t[lp.pos].val-t[now.pos].val;
                    lp.v=b[t[lp.pos].id].y;
                    hp.push(lp);
                }
                if(t[now.pos].rs){
                    sol lp=now;
                    lp.pos=t[lp.pos].rs;
                    lp.val+=t[lp.pos].val-t[now.pos].val;
                    lp.v=b[t[lp.pos].id].y;
                    hp.push(lp);
                }
            }
        }
        ot(ans);
        return 0;
    }
    
    }
    signed main(){
        Miracle::main();
        return 0;
    }
    
    /*
       Author: *Miracle*
    */

转载于:https://www.cnblogs.com/Miracevin/p/10878400.html

[http_www.docin.com_p-1387370338.html]: http://www.docin.com/p-1387370338.html