P2483 【模板】k 短路 / [SDOI2010] 魔法猪学院-北京尧图网络

题意给出一张nnn个点mmm条边的有向带权图求出最大的kkk满足前kkk短路径加长度起来大于EEE。n≤5010n\le5010n≤5010m≤2×105m\le2\times10^5m≤2×105E≤107E\le10^7E≤107边权w≤Ew\le Ew≤E。思路先用dijdijdij在反图上跑建一个以nnn为根的最短路树对于一个点uuu定义d(u)d(u)d(u)为uuu到nnn的最短路长度。对于一条边(u,v,w)(u,v,w)(u,v,w)定义祂的新权值w′wd(v)−d(u)wwd(v)-d(u)w′wd(v)−d(u)。对于一条路径把路径上的非最短路树边按照顺序领出来设为(u1,v1),(u2,v2),…(u_1,v_1),(u_2,v_2),\dots(u1,v1),(u2,v2),…那么对于每个iii有ui1u_{i1}ui1是viv_ivi在最短路树上的祖先而这条路径的边权和为d(s)d(s)d(s)加所有非最短路树边的新权值和。现在来考虑一个暴力在每个点uuu上存所有以uuu的某个祖先为起点的非最短路树边用一个优先队列存现在有哪些路经每次选最短的取出来并把祂能到直接达的所有点放进优先队列。显然这样是过不了的但是可以用可持久化可并堆优化。具体的每个点开可并小根堆存以这个点祖先为起点的所有非最短路树边。显然同一个堆中只有堆顶需要放进优先队列。在把一个路径取出来时只需要把祂在堆上的左右儿子和祂存的边能到达的点加入优先队列。代码// Problem: P2483 【模板】k 短路 / [SDOI2010] 魔法猪学院// Contest: Luogu// URL: https://www.luogu.com.cn/problem/P2483// Memory Limit: 128 MB// Time Limit: 1000 ms//// Powered by CP Editor (https://cpeditor.org)#includebits/stdc.husingnamespacestd;namespaceIO{templatetypenameTinlinevoidread(Tx){x0;charcgetchar();boolf0;while(!isdigit(c))c-?f1:0,cgetchar();while(isdigit(c))xx*10c-0,cgetchar();f?x-x:0;}templatetypenameTinlinevoidwrite(T x){if(x0){putchar(0);return;}x0?x-x,putchar(-):0;shortst[50],top0;while(x)st[top]x%10,x/10;while(top)putchar(st[top--]0);}inlinevoidread(charc){cgetchar();while(isspace(c))cgetchar();}inlinevoidwrite(charc){putchar(c);}inlinevoidread(doublex){scanf(%lf,x);}inlinevoidwrite(doublex){printf(%lf,x);}inlinevoidread(strings){s.clear();charc;read(c);while(!isspace(c)~c)sc,cgetchar();}inlinevoidwrite(string s){for(inti0,lens.size();ilen;i)putchar(s[i]);}templatetypenameTinlinevoidwrite(T*x){while(*x)putchar(*(x));}templatetypenameT,typename...T2inlinevoidread(Tx,T2...y){read(x),read(y...);}templatetypenameT,typename...T2inlinevoidwrite(constT x,constT2...y){write(x),putchar( ),write(y...),sizeof...(y)1?putchar(\n):0;}}usingnamespaceIO;constintmaxn5010,maxm200010;constdoubleeps1e-8;intn,m,fa[maxn],rt[maxn];doubleE,dis[maxn];structEDGE{intu,v;doublew;}b[maxm];vectorpairint,doublee[maxn],ef[maxn];vectorinttr[maxn];boolflag[maxn],in[maxn];namespaceLeftist_Tree{structnode{intch[2],dist,to;doubleval;}t[maxm*20];intcnt;intmerge(intu,intv){if(!u||!v)returnuv;if(t[u].valt[v].val)swap(u,v);intclonecnt;t[clone]t[u];t[clone].ch[1]merge(t[u].ch[1],v);if(t[t[clone].ch[0]].distt[t[clone].ch[1]].dist)swap(t[clone].ch[0],t[clone].ch[1]);t[clone].distt[t[clone].ch[1]].dist1;returnclone;}};voiddij(ints){priority_queuepairdouble,intq;for(inti1;in;i)dis[i]1e15;dis[s]0;q.push({0,s});while(!q.empty()){auto[l,u]q.top();q.pop();if(flag[u])continue;flag[u]1;for(auto[v,w]:ef[u])if(dis[v]dis[u]w)dis[v]dis[u]w,q.push({-dis[v],v});}}voiddfs(intu){for(intv:tr[u]){rt[v]Leftist_Tree::merge(rt[u],rt[v]);dfs(v);}}priority_queuepairdouble,int,vectorpairdouble,int,greaterpairdouble,intqu;signedmain(){read(n,m,E);for(inti1;im;i){intu,v;doublew;read(u,v,w);if(un)w1e15;e[u].push_back({v,w}),ef[v].push_back({u,w});b[i]{u,v,w};}dij(n);for(inti1;in;i)for(auto[v,w]:ef[i])if(abs(dis[v]-dis[i]-w)eps)fa[v]i;for(inti1;in;i)if(dis[i]1e14)in[i]1;for(inti1;im;i){auto[u,v,w]b[i];if((fa[u]vabs(dis[u]-(dis[v]w))eps))continue;wwdis[v]-dis[u];if(in[u]in[v]){intd;Leftist_Tree::t[dLeftist_Tree::cnt]{{0,0},0,v,w};if(rt[u]0)rt[u]d;elsert[u]Leftist_Tree::merge(rt[u],d);}}for(inti1;in;i)if(in[i]fa[i])tr[fa[i]].push_back(i);dfs(n);intans1;E-dis[1];qu.push({dis[1]Leftist_Tree::t[rt[1]].val,rt[1]});while(!qu.empty()){auto[l,u]qu.top();qu.pop();E-l;if(E0)break;ans;if(Leftist_Tree::t[u].ch[0])qu.push({l-Leftist_Tree::t[u].valLeftist_Tree::t[Leftist_Tree::t[u].ch[0]].val,Leftist_Tree::t[u].ch[0]});if(Leftist_Tree::t[u].ch[1])qu.push({l-Leftist_Tree::t[u].valLeftist_Tree::t[Leftist_Tree::t[u].ch[1]].val,Leftist_Tree::t[u].ch[1]});intdrt[Leftist_Tree::t[u].to];if(d)qu.push({lLeftist_Tree::t[d].val,d});}write(ans);return0;}

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

相关推荐

深入解析AMD Ryzen SMU调试工具：从硬件底层到性能优化的完整指南

4.19华为OD机试真题新系统 - 分辨率排序 (JavaPyCC++JsGo)

2026会计岗位职场能力培训课程

更多资讯

五大行业迁移实战：PolarDB-X分布式数据库落地与架构设计

Claudian Obsidian 插件完整安装指南：把 Claude Code 装进你的知识库

基于Java springboot化妆品推荐系统(源码+lw+部署文档+讲解等)

2026车规芯片选型：从参数对标到系统可信度验证

基于Java springboot货运通服务平台系统(源码+lw+部署文档+讲解等)

G-Helper 配置重置指南：模式失灵、风扇不听使唤时，3 级修复让它重新可用

今日更新

Linux 内核 ARM 虚拟内存布局全解析：从 4GB 地址空间划分到源码级验证

AIGC降重工具测评与教育应用指南

数据容灾核心指标与实战方案解析

本周精选

超人会飞不算本事：系统稳定依赖清晰规则与边界设计

超人VS蜘蛛侠：拆解超级IP的影响力与传播方法论

基于CNN的调制信号识别：MATLAB实现时频图分类实战

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？