精华内容
下载资源
问答
  • 可持久化左偏树

    2019-09-22 15:30:14
    顺手学的可持久化左偏树倒是容易,来写一发 基本思路就是每次merge的时候将普通左偏树里准备作为新的根的结点copy一个,对新结点搞事 然后所有操作基于merge 然后就没了( 最近比较懒不想写泛型和OOP,OIer码风将就...

    闲来无事想学k短路,但看着很难打(

    顺手学的可持久化左偏树倒是容易,来写一发

    基本思路就是每次merge的时候将普通左偏树里准备作为新的根的结点copy一个,对新结点搞事

    然后所有操作基于merge

    然后就没了(

    最近比较懒不想写泛型和OOP,OIer码风将就一下(

    什么时候写好了泛型单独放代码

    struct Node
    {
        int val;
        Node *lc,*rc;
        int npl;
        Node(int v):
            val(v),
            lc(NULL),
            rc(NULL),
            npl(1)
        {}
    };
    
    Node *root[1<<10];
    int vertot;
    
    Node *merge(Node *l,Node *r)
    {
        if(l==NULL)return r;
        if(r==NULL)return l;
        if(l->val>r->val)std::swap(l,r);
        Node *ptr=new Node(*l);//全文与普通左偏树唯一的不同之处
        ptr->rc=merge(ptr->rc,r);
        if(ptr->lc==NULL||ptr->lc->npl<ptr->rc->npl)
        {
            std::swap(ptr->lc,ptr->rc);
        }
        ptr->npl=ptr->rc!=NULL?ptr->rc->npl+1:1;
        return ptr;
    }
    
    Node *push(int val,Node *rt)
    {
        return merge(new Node(val),rt);
    }
    
    int top(Node *rt)
    {
        return rt->val;
    }
    
    Node *pop(Node *rt)
    {
        return merge(rt->lc,rt->rc);
    }
    
    展开全文
  • 利用可持久化左偏树(每次合并的时候新建节点即可),对于每一个点维护一棵小根堆左偏树,里面储存从该点走树边走到终点的路径上,与这条路径相连的非树边有哪些。 首先,第1短路是从S开始不走非树边的路。开一个优先...

    题目大意

    有一堆项目,每个项目有三个权值 ( c o s t 0 , c o s t 1 , c o l o r ) (cost_0,cost_1,color) (cost0,cost1,color),你要选择一些项目顺序执行,并给出你总花费的计算方式,求花费第k 的工作方式。

    题目分析

    建图

    转化为求k短路的话,必须要把权值取相反数,然后答案取相反数。

    把每个项目 i i i拆成三个点 i 1 i_1 i1, i 2 i_2 i2, i 3 i_3 i3,连边 ( i 1 , i 3 , − c o s t 0 ) ( i 2 , i 3 , − c o s t 1 ) (i_1,i_3,-cost_0)(i_2,i_3,-cost_1) (i1,i3,cost0)(i2,i3,cost1)表示两种花钱方式,根据i的color连边 ( i 3 , ( i + 1 ) 1 , 0 ) (i_3,(i+1)_1,0) (i3,(i+1)1,0) ( i 3 , ( i + 1 ) 1 , 0 ) (i_3,(i+1)_1,0) (i3,(i+1)1,0),连边 ( i 1 , ( i + 1 ) 1 , 0 ) ( i 2 , ( i + 1 ) 2 , 0 ) (i_1,(i+1)_1,0)(i_2,(i+1)_2,0) (i1,(i+1)1,0)(i2,(i+1)2,0)表示不做这个项目.
    起点为 1 1 1_1 11,新建终点, n 1 n_1 n1, n 2 n_2 n2, n 3 n_3 n3连到终点上。

    可持久化左偏树

    首先由于图的性质,可以通过拓扑计算从终点到其他点在反向图上的最短路,即为该点在正向图上走最短路到终点的距离 d i s dis dis.这一步上,我们也建立出了一棵终点的最短路树,分出了非树边与树边。

    然后我们希冀每走一步就能获得一条新的当前最短路径的算法。

    我们知道,走一条路,那便是走若干树边和若干非树边.所以我们的更新可以是每次在当前路径的基础上多走一条非树边。

    设非树边 ( u , v ) (u,v) (u,v)的权值为 d i s v + w ( u , v ) − d i s u dis_v+w(u,v)-dis_u disv+w(u,v)disu,即减去原来这一段都走树边的贡献,加上走一条非树边的贡献。

    利用可持久化左偏树(每次合并的时候新建节点即可),对于每一个点维护一棵小根堆左偏树,里面储存从该点走树边走到终点的路径上,与这条路径相连的非树边有哪些。

    首先,第1短路是从S开始不走非树边的路。开一个优先队列,来维护现在的“第 t t t短路候选路径”,求第 t t t短路时,就从这个候选队列里取出最短的一条路径作为第 t t t短路径。在确定了第 t t t短路径后,有几条比该路径稍长的路径也该被加入候选队列中,它们是:

    1. 在走了第 t t t短路径上的最后一条非树边后,假设我站在 v v v这个点上,那么我在我剩下的前进道路中,再选一条非树边走一下。
    2. 不走第 t t t短路径的最后一条非树边,而是走它在堆中的左儿子/右儿子。

    于是这个候选队列中存放的候选路径的信息就只有,路径长度和走的最后一条非树边了。

    可能有点没讲清楚,具体可以看一下work函数。

    代码

    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<queue>
    using namespace std;
    int read() {
    	int q=0;char ch=' ';
    	while(ch<'0'||ch>'9') ch=getchar();
    	while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
    	return q;
    }
    #define LL long long
    #define pr pair<LL,int>
    const int N=150005;
    const LL inf=1e15;
    int T,n,K,s,t,t0,t1,tot,top;
    int h0[N],h1[N],pre[N],rt[N],st[N],du[N];LL dis[N];
    struct edge{int w,to,ne;}e0[N<<1],e1[N<<1];
    void add(int x,int y,int z) {
    	e0[++t0].to=y,e0[t0].ne=h0[x],h0[x]=t0,e0[t0].w=z;
    	e1[++t1].to=x,e1[t1].ne=h1[y],h1[y]=t1,e1[t1].w=z;
    	++du[x];
    }
    void bg() {//build_graph
    	s=n+1,t=n*3+1;int c0,c1,co;
    	t0=t1=0;for(int i=1;i<=t;++i) h0[i]=h1[i]=du[i]=0,dis[i]=inf;
    	for(int i=1;i<=n;++i) {
    		c0=read(),c1=read(),co=read();
    		add(n+i,i,-c0),add(n+n+i,i,-c1);
    		if(i!=n) {
    			add(n+i,n+i+1,0),add(n+n+i,n+n+i+1,0);
    			if(co) add(i,n+n+i+1,0);
    			else add(i,n+i+1,0);
    		}
    		else add(n,t,0),add(n+n,t,0),add(n+n+n,t,0);
    	}
    }
    void topo() {
    	top=1,st[top]=t,dis[t]=pre[t]=0;
    	while(top) {
    		int x=st[top--];
    		for(int i=h1[x];i;i=e1[i].ne) {
    			if(dis[e1[i].to]>dis[x]+e1[i].w)
    				dis[e1[i].to]=dis[x]+e1[i].w,pre[e1[i].to]=x;
    			--du[e1[i].to];if(!du[e1[i].to]) st[++top]=e1[i].to;
    		}
    	}
    }
    struct node{int ls,rs,d,id;LL v;}a[N*40];
    int merge(int x,int y) {
    	if(x*y==0) return x+y;
    	if(a[x].v>a[y].v) swap(x,y);
    	int o=++tot;a[tot]=a[x];
    	a[o].rs=merge(a[o].rs,y);
    	if(a[a[o].ls].d<a[a[o].rs].d) swap(a[o].ls,a[o].rs);
    	a[o].d=a[a[o].rs].d+1;
    	return o;
    }
    void dfs(int x) {//每个左偏树代表从i到t的路上的所有非树边
    	if(pre[x]) rt[x]=rt[pre[x]];
    	for(int i=h0[x];i;i=e0[i].ne) {
    		int v=e0[i].to;
    		if(dis[v]==inf||pre[x]==v) continue;
    		a[++tot]=(node){0,0,1,v,dis[v]+e0[i].w-dis[x]},rt[x]=merge(rt[x],tot);
    	}
    	for(int i=h1[x];i;i=e1[i].ne)
    		if(pre[e1[i].to]==x) dfs(e1[i].to);
    }
    void work() {
    	tot=0,rt[t]=0,dfs(t);
    	if(K==1) {printf("%lld\n",-dis[s]);return;}
    	priority_queue<pr,vector<pr >,greater<pr > > q;
    	q.push(pr(dis[s]+a[rt[s]].v,rt[s]));
    	while(K--) {//利用优先队列获得答案
    		pr kl=q.top(); q.pop();
    		if(K==1) {printf("%lld\n",-kl.first);return;}
    		int u=kl.second,v=a[u].id;
    		if(rt[v]) q.push(pr(kl.first+a[rt[v]].v,rt[v]));
    		if(a[u].ls) q.push(pr(kl.first-a[u].v+a[a[u].ls].v,a[u].ls));
    		if(a[u].rs) q.push(pr(kl.first-a[u].v+a[a[u].rs].v,a[u].rs));
    	}
    }
    int main() {
    	T=read();
    	while(T--) {
    		n=read(),K=read();
    		bg(),topo(),work();
    	}
        return 0;
    }
    
    展开全文
  • 题面: 题目大意:给你一张有向图,求1到n的第k短路 $K$短路模板题 ...我们加入一条非边,它对于答案的贡献就是$delta(u,v)=dis[v]+e(u,v)-dis[u]$,即如果选择了这条边,这条路径的长度就会增加$delta...

    题面:

    题目大意:给你一张有向图,求1到n的第k短路

    $K$短路模板题

    假设整个图的边集为$G$

    首先建出以点$n$为根的,沿反向边跑的最短路树,设这些边构成了边集$T$

    那么每个点沿着树边走到点$n$,它对于答案的贡献为0

    我们加入一条非树边,它对于答案的贡献就是$delta(u,v)=dis[v]+e(u,v)-dis[u]$,即如果选择了这条边,这条路径的长度就会增加$delta(u,v)$

    那么一条路径$p$的总长度就是$dis_{min}+\sum\limits_{e\in p,e\in G-T} delta(e)$

    我们现在要求出前$K$条总长度最小的路径长度,(即使在这道题里我们不知道K是多少)

    我们首先向一个堆中加入一条非树边,然后依次拓展,拓展的过程是这样的:

    每次从堆中取出一条边集$p$,然后有两种情况

    1.把末尾这条边替换成,这条边原来所在的边集里,边权大于等于它的一条边

    2.新加入一条,末尾这条边的终点$v$,在最短路树里的一个祖先所能扩展的一条最短的非树边

    这样扩展保证了每次新产生的边集贡献$\geq $原来的边集贡献,保证了有序性

    且每次都选择最短的边集,保证了同一种边集不会重复讨论

    第二个操作需要找出最小的后继状态,而后继状态可能很多,想办法用数据结构维护

    在最短路树上每个点都维护反向非树边的集合,那么子节点也要包含父节点的集合,需要可持久化

    而对于第一个操作,我们需要一个有序表来扩展,所以要用到堆之类的东西

    可持久化可并堆!

    无非就是$merge$里每次合并都新建节点罢了

    第一个操作就是把最后一条边换成这条边在堆中的左右儿子

    第二个操作直接取堆顶即可

    这也是类似于普通$dijkstra$最短路的扩展过程

     

      1 #include <queue>
      2 #include <cmath>
      3 #include <vector>
      4 #include <cstdio>
      5 #include <cstring>
      6 #include <algorithm>
      7 #define N1 5010
      8 #define M1 200010
      9 #define S1 N1<<8
     10 #define ll long long 
     11 #define dd double
     12 using namespace std;
     13 const dd eps=1e-7;
     14 
     15 template <typename _T> void read(_T &ret)
     16 {
     17     ret=0; _T fh=1; char c=getchar();
     18     while(c<'0'||c>'9'){ if(c=='-') fh=-1; c=getchar(); }
     19     while(c>='0'&&c<='9'){ ret=ret*10+c-'0'; c=getchar(); }
     20     ret=ret*fh;
     21 }
     22 
     23 int n,m;
     24 struct Edge{
     25 int to[M1<<1],nxt[M1<<1],val[M1<<1],head[N1],cte; dd dis[M1<<1];
     26 void ae(int u,int v,dd d)
     27 {
     28     cte++; to[cte]=v; nxt[cte]=head[u];
     29     head[u]=cte; dis[cte]=d;
     30 }
     31 }e; 
     32 
     33 
     34 struct node1{
     35 int x; dd d;
     36 node1(int x,dd d):x(x),d(d){} node1(){}
     37 friend bool operator < (const node1 &s1,const node1 &s2)
     38 {
     39     return s1.d>s2.d;
     40 }
     41 };
     42 
     43 struct Heap{
     44 int ch[S1][2],h[S1],root0[N1],root1[N1],tot; node1 val[S1];
     45 int merge0(int x,int y)
     46 {
     47     if(!x||!y) return x+y;
     48     if(val[x]<val[y]) swap(x,y);
     49     ch[x][1]=merge0(ch[x][1],y);
     50     if(h[ch[x][0]]<h[ch[x][1]]) swap(ch[x][0],ch[x][1]);
     51     h[x]=h[ch[x][1]]+1;
     52     return x;
     53 }
     54 int merge1(int x,int y)
     55 {
     56     if(!x||!y) return x+y;
     57     if(val[x]<val[y]) swap(x,y);
     58     int nx=++tot; val[nx]=val[x]; ch[nx][0]=ch[x][0]; ch[nx][1]=ch[x][1]; h[nx]=h[x];
     59     ch[nx][1]=merge1(ch[x][1],y);
     60     if(h[ch[nx][0]]<h[ch[nx][1]]) swap(ch[nx][0],ch[nx][1]);
     61     h[nx]=h[ch[nx][1]]+1;
     62     return nx;
     63 }
     64 }h;
     65 
     66 priority_queue<node1>q;
     67 int use[N1]; dd dis[N1];
     68 void dijkstra()
     69 {
     70     node1 k; int x,j,v;
     71     q.push(node1(n,0)); dis[n]=0;
     72     for(j=1;j<n;j++) dis[j]=666666666;
     73     while(!q.empty())
     74     {
     75         k=q.top(); q.pop(); x=k.x; 
     76         if(use[x]) continue; use[x]=1;
     77         for(j=e.head[x];j;j=e.nxt[j])
     78         {
     79             v=e.to[j]; 
     80             if(dis[v]-eps>dis[x]+e.dis[j])
     81             {
     82                 dis[v]=dis[x]+e.dis[j];
     83                 q.push(node1(v,dis[v]));
     84             }
     85         }
     86     }
     87 }
     88 int fa[N1],de; dd la[N1];
     89 void dfs_tree(int x)
     90 {
     91     int j,v;
     92     if(fa[x]) h.root1[x]=h.merge1(h.root1[fa[x]],h.root0[x]);
     93     for(j=e.head[x];j;j=e.nxt[j])
     94     {
     95         v=e.to[j]; if(!e.val[j]) continue;
     96         dfs_tree(v);
     97     }
     98 }
     99 void build_tree()
    100 {
    101     int i,x,j,v;
    102     for(i=1;i<=n;i++) 
    103     {
    104         for(j=e.head[i];j;j=e.nxt[j])
    105         {
    106             v=e.to[j]; 
    107             if(!fa[v]&&fabs(dis[i]+e.dis[j]-dis[v])<eps)
    108                 e.val[j]^=1, fa[v]=i;
    109         }
    110     }
    111     for(x=1;x<=n;x++) 
    112     {
    113         for(j=e.head[x];j;j=e.nxt[j])
    114         {
    115             v=e.to[j]; if(e.val[j]) continue;
    116             h.val[++h.tot]=node1(x,dis[x]+e.dis[j]-dis[v]);
    117             h.root0[v]=h.merge0(h.root0[v],h.tot);
    118         }
    119     }
    120 }
    121 dd E;
    122 struct node2{
    123 int x,v; dd d,D;
    124 node2(int x,int v,dd d,dd D):x(x),v(v),d(d),D(D){} node2(){}
    125 friend bool operator < (const node2 &s1,const node2 &s2)
    126 {
    127     return s1.D>s2.D;
    128 }
    129 };
    130 priority_queue<node2>que;
    131 
    132 void debug()
    133 {
    134     int x=1; 
    135     while(fa[x]) printf("%d ",fa[x]), x=fa[x];
    136     puts("");
    137 }
    138 
    139 int main()
    140 {
    141     //freopen("testdata.in","r",stdin);
    142     scanf("%d%d%lf",&n,&m,&E);
    143     int i,j,k,x,y,v,xx,vv,ans=0; dd d,now,w; 
    144     for(i=1;i<=m;i++) 
    145     {
    146         read(x), read(y), scanf("%lf",&d);
    147         e.ae(y,x,d); 
    148     }
    149     dijkstra();
    150     build_tree();
    151     dfs_tree(n);
    152     node2 K;
    153     que.push(node2(0,1,0,0)); ans=0;
    154     //debug();
    155     while(!que.empty())
    156     {
    157         K=que.top(); que.pop(); x=K.x; v=K.v; E-=K.D+dis[1]; 
    158         //printf("%lf\n",K.D+dis[1]);
    159         if(E>-eps) ans++; else break;
    160         if(h.root1[v]) 
    161         {
    162             j=h.root1[v]; vv=h.val[j].x; w=h.val[j].d;
    163             que.push(node2(j,vv,w,K.D+w));
    164         }
    165         if(h.ch[x][0])
    166         {
    167             j=h.ch[x][0]; vv=h.val[j].x; w=h.val[j].d;
    168             que.push(node2(j,vv,w,K.D-K.d+w));
    169         }
    170         if(h.ch[x][1])
    171         {
    172             j=h.ch[x][1]; vv=h.val[j].x; w=h.val[j].d;
    173             que.push(node2(j,vv,w,K.D-K.d+w));
    174         }
    175     }
    176     printf("%d\n",ans);
    177     return 0;
    178 }

     

    转载于:https://www.cnblogs.com/guapisolo/p/10463965.html

    展开全文
  • 传送门 解析: 一发AC,然后按照惯例开O2交了一发,就是为了冲榜。 WOC怎么这么多人比我快。。。 然后一看代码,WOC怎么还有A∗A*A∗跑得比我快的。。。 结果他们都是面向数据编程。...然后我加了个特判交了...

    传送门


    解析:

    一发AC,然后按照惯例开O2交了一发,就是为了冲榜。

    WOC怎么这么多人比我快。。。

    然后一看代码,WOC怎么还有 A ∗ A* A跑得比我快的。。。

    结果他们都是面向数据编程。。。

    加了这个特判:

    if(fabs(E-10000000)<1e-6){
    	printf("2002000\n");
    	return 0;	
    }
    

    把最大的那个点给糊弄过去了。。。

    然后我加了个特判交了一发。

    rank2。。。

    额前面这个ID怎么这么眼熟,额他的空间怎么这么小? 2 M B 2MB 2MB

    额,没错就是几个月之前闹出来的自动AC机(直接偷取答案文件并输出)。。。

    也就是说,不算自动AC机,我这份代码(加上特判)应该是全洛谷跑得最快的了。


    解析:

    一看是不是一个裸的K短路啊,然而洛谷大佬加强了数据。。。。

    然后放宽了空间。。。

    所以这道题需要一个复杂度较为严格的做法。

    关于 K K K短路可以直接去我这篇博客上看:https://blog.csdn.net/zxyoi_dreamer/article/details/86632445

    这里显然就是尽量跑权值在前面的,然后去减就好了。


    代码:

    #include<bits/stdc++.h>
    #include<ext/pb_ds/priority_queue.hpp>
    using namespace std;
    #define ll long long
    #define re register
    #define gc get_char
    #define cs const
    
    namespace IO{
        inline char get_char(){
            static cs int Rlen=1<<20|1;
            static char buf[Rlen],*p1,*p2;
            return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,Rlen,stdin),p1==p2)?EOF:*p1++;
        }
        
        inline int getint(){
            re char c;
            while(!isdigit(c=gc()));re int num=c^48;
            while(isdigit(c=gc()))num=(num+(num<<2)<<1)+(c^48);
            return num;
        }
        inline double getdb(){
            re char c;
            while(!isdigit(c=gc()));re double x=c^48;
            while(isdigit(c=gc()))x=x*10+(c^48);
            if(c!='.')return x;
            re double y=1.0;
            while(isdigit(c=gc()))x+=(y/=10)*(c^48);
            return x;
        }
    }
    using namespace IO;
    
    cs int N=5003,M=200005,B=20;
    int n,m,S=1,T;
    
    struct Graph{
        int last[N],nxt[M],to[M],ecnt;
        double w[M];
        inline void addedge(int u,int v,double val){
            nxt[++ecnt]=last[u],last[u]=ecnt,to[ecnt]=v,w[ecnt]=val;
        }
    }g,rg;
    
    double dist[N];
    
    inline void Dij(){
        static cs int *last=rg.last,*to=rg.to,*nxt=rg.nxt;
        static cs double *w=rg.w;
        
        memset(dist,127,sizeof dist);
        set<pair<double,int> > q;
        q.insert(make_pair(dist[T]=0,T));
        while(!q.empty()){
            int u=q.begin()->second;q.erase(q.begin());
            for(int re e=last[u],v=to[e];e;v=to[e=nxt[e]])
            if(dist[v]>dist[u]+w[e]){
                q.erase(make_pair(dist[v],v));
                q.insert(make_pair(dist[v]=dist[u]+w[e],v));
            }
        }
    }
    
    bool tree_edge[M],vis[N];
    int fa[N],st[N],top;
    
    void dfs(int u){
        static cs int *last=rg.last,*nxt=rg.nxt,*to=rg.to;
        static cs double *w=rg.w;
        
        st[++top]=u;
        vis[u]=true;
        for(int re e=last[u],v=to[e];e;v=to[e=nxt[e]])
        if(!vis[v]&&fabs(dist[v]-dist[u]-w[e])<1e-6){
            fa[v]=u;tree_edge[e]=true;
            dfs(v);
        }
    }
    
    namespace LT{
        int son[M*B][2];
        int ht[M*B],id[M*B];
        double val[M*B];
        int tot;
        
        inline int newnode(double _val,int _id,int _dis=0){
            int now=++tot;
            val[now]=_val,id[now]=_id;
            ht[now]=_dis,son[now][0]=son[now][1]=0;
            return now;
        }
        
        inline int _copy(int ori){
            int now=++tot;
            val[now]=val[ori],id[now]=id[ori];
            ht[now]=ht[ori],son[now][0]=son[ori][0],son[now][1]=son[ori][1];
            return now;
        }
        
        inline int merge(int a,int b){
            if(!a||!b)return a|b;
            if(val[a]>val[b])swap(a,b);
            int now=_copy(a);
            son[now][1]=merge(son[now][1],b);
            if(ht[son[now][0]]<ht[son[now][1]])swap(son[now][0],son[now][1]);
            ht[now]=ht[son[now][1]]+1;
            return now;
        }
        
        inline void insert(int &rt,double val,int id){
            rt=merge(rt,newnode(val,id));
        }
    }
    
    int rt[N];
    
    inline void build_heap(){
        static cs int *last=g.last,*to=g.to,*nxt=g.nxt;
        static cs double *w=g.w;
        
        for(int re i=1,u;i<=top;++i){
            u=st[i];
            rt[u]=rt[fa[u]];
            for(int re e=last[u],v=to[e];e;v=to[e=nxt[e]])
            if(!tree_edge[e]&&dist[v]<1e9)LT::insert(rt[u],dist[v]-dist[u]+w[e],v);
        }
    }
    
    double E;
    inline int calc_K(){
        int ans=1;E-=dist[S];
        __gnu_pbds::priority_queue<pair<double,int> ,greater<pair<double,int> > > q;
        q.push(make_pair(dist[S]+LT::val[rt[S]],rt[S]));
        while(!q.empty()){
            pair<double,int> qq=q.top();q.pop();
            double v=qq.first;
            E-=v;
            if(E>=0)++ans;
            else return ans;
            int u=qq.second,o=LT::id[u];
            int lc=LT::son[u][0],rc=LT::son[u][1];
            if(rt[o])q.push(make_pair(v+LT::val[rt[o]],rt[o]));
            if(lc)q.push(make_pair(v+LT::val[lc]-LT::val[u],lc));
            if(rc)q.push(make_pair(v+LT::val[rc]-LT::val[u],rc));
        }
        return ans;
    }
    
    signed main(){
        S=1,T=n=getint(),m=getint();E=getdb();
        while(m--){
            int u=getint(),v=getint();
            double val=getdb();
            g.addedge(u,v,val);
            rg.addedge(v,u,val);
        }
        Dij();
        dfs(T);
        build_heap();
        cout<<calc_K();
        return 0;
    }
    
    展开全文
  • A的做法不大稳定,因此采取可持久化左偏树的做法来优化A 时间复杂度O(nlogn+mlogm+klogk)O(nlogn+mlogm+klogk)O(nlogn+mlogm+klogk) #include<cstdio> #include<cstring> #include<iostream> #...
  • 【NOI集训】【XJ】可持久化左偏树

    千次阅读 2015-07-05 21:03:47
    http://hzxjhs.com:83/contest/456... 果断并堆 #include #include #include #include #include #include #define Rep(i, x, y) for (int i = x; i ; i ++) #define RepE(i, x) for (int i = pos[x]; i; i =
  • 不过有个更优复杂度的思路(用可持久化可并堆做)可以看看 #include&amp;amp;amp;lt;cstdio&amp;amp;amp;gt; #include&amp;amp;amp;lt;iostream&amp;amp;amp;gt; #include&amp;amp;amp;lt;...
  • 题目链接:Subsequence吐槽,先是对着定义yy了持久化二项堆,然后发现不好搞这个k短路,然后找了左偏树的定义,对着yy了20分钟写出了可持久化左偏树,然后过了poj2449后就1A了这个题。#include #include #...
  • 不能和祖先的边混合,这是为了转移Ⅰ,替换最后一条边 那么可持久化即可 ⚠:最后注意一下,以 n n n为起点的边(这种魔法可以将 n n n元素转化成其他元素)是不能要的 因为本题,到了 n n n元素就意味着这次转化...
  • 可持久化堆写了一遍.在K很小的时候似乎和A*时间差别并不大. 但是当K大了以后.A*和可持久化堆根本无法同台竞技.Sigh. /* I will wait for you */ #include #include #include #include #include #...
  • 将每个点的并堆像线段合并的可持久化一样与子节点的堆合并即可。 $bzoj$与$luogu$的精度不同,代码附上两个版本的。 $bzoj$ #include #include #include #include #include #include #include #include ...
  • 左偏树模板

    2017-05-14 23:00:00
    概要:左偏树是具有左偏性质的堆有序二叉树,它相比于优先队列,能够实现合并堆的功能。 先orz国家集训队论文https://wenku.baidu.com/view/515f76e90975f46527d3e1d5.html 左偏树的几个基本性质如下: 节点...
  • 不得不说,这道题目是真的难,真不愧它的“省选/NOI-”的紫色大火题!!!...至少我一开始不知道为什么要用左偏树,甚至我看题解一开始也都没弄懂,所以先把题目弄清楚。 首先我们由题可以...
  • 题目链接 ...分析 题目要求堆支持合并操作,左偏树是一种实现方式; 具体来说,除了要保证堆的根...一般来说,左偏树只需递归实现合并操作,其他操作便轻易完成。 AC代码 #include <cstdio> #include <iostr...
  • 并堆之左偏树总结

    2016-07-28 21:50:02
    并堆之左偏树总结 左偏树,顾名思义,是左边的结点权值较大的树形数据结构。主要用于两个优先队列的快速合并,是并堆的一种实现方式。 定义与性质: 外结点:一个结点的右子结点为空就为外结点 ...
  • 左偏树

    2021-01-28 08:50:35
    可持久化左偏树 例题:K短路 见K短路模板 例题:【弱省胡策】Round #1 OVOO 题目大意:给定一棵树,求包含节点 111 ,边权和第 KKK 小且连通的导出子图的边权和。 以节点 111 为根,对于每个节点建立一棵左偏树,...
  • 左偏树合并的二叉堆,首先满足所有的堆的性质,其外,它还可以合并。左偏树的树节点需要保存的信息有: 1.左右子树节点编号 2.此节点到有空子结点的结点的最短距离len 3.自身权值首先...
  • 并堆之左偏树

    2018-11-07 22:32:00
    并堆有多种,包括斜堆,左偏树,二项堆,配对堆,斐波那契堆等。 这里我们只介绍左偏树($Leftist\ Tree$),它是最常用的一种并堆。至于为什么说最常用,我们会在后面讲到。(先挖个坑) 讲的可能不太好还请...
  • 通常我们使用的二叉堆,是用一个数组实现的完全二叉树,对于查询有O(1)复杂度,对于插入、删除有O(logn)复杂度 而且常数比较小,是一个比较优秀的数据结构 但是。 当我们需要合并两个堆的时候,用...在介绍左偏树之前
  • 配对堆的核心要义在于合并, 关键在于保证的偏向性。
  • 可持久化数据结构

    2020-05-27 22:13:48
    可持久化数据结构 1. 概念 完全可持久化:可以支持查询、修改历史版本数据的数据结构。 部分可持久化:可以支持查询历史版本,但修改仅限于当前版本的数据结构。 2. 记号 2.1. 复杂度分析: ​ 无修改时: 采用O(A)+...
  • 基本知识:普通堆,二叉搜索可持久化基本思想。 介绍 性质 Treap = Tree + Heap Treap 是一颗同时拥有二叉搜索和堆性质的一颗二叉树 Treap 有两个关键字,在这里定义为: key\text{key}key:满足...
  • 题意:给出一个带权有向图。求一个最大的K使得前K短路的长度之和不大于给定的值Sum。 思路:首先,求出每个点到n的最短路。接着,使用优先队列,节点为(D,u)。首先将(dis[1],1)进队。由于D在任意时候为一条1到n的...
  • 左偏树的合并过程差不多, 也非常简洁。 3.第k大 因为我们维护了每个节点的siz信息, 直接像splay一样递归下去找就行了 int kth( int k, int now) { if (k == siz[tree[now][ 0 ]] + 1 ) ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,085
精华内容 1,234
关键字:

可持久化左偏树