当前位置: 首页 > 编程日记 > 正文

Bzoj4016: [FJOI2014]最短路径树问题

题面

传送门

Sol

\(SPFA\)求出单源最短路,\(Bfs\)建出树,字典序可以用堆解决
然后就是点分治的一眼题
开桶记录到当前根经过边长度相同的最长路,记录它的长度


自己强行\(yy\)了一个这种类型的点分丑陋写法

# include <bits/stdc++.h>
# define RG register
# define IL inline
# define Fill(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll;
const int _(2e5 + 5);IL int Input(){RG int x = 0, z = 1; RG char c = getchar();for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);return x * z;
}int n, m, k, mx[_], root, size[_], vis[_], tot, dis[_];
struct Edge{int to[_], w[_], next[_], first[_], cnt;IL void Init(){Fill(first, -1);}IL void Add(RG int u, RG int v, RG int ww){to[cnt] = v, next[cnt] = first[u], w[cnt] = ww, first[u] = cnt++;}
} G1, G2;
int deep[_], len[_], t[_], num[_], S1[_], S2[_];
ll ans1, ans2;
queue <int> Q;
priority_queue <int> H;IL void GetRoot(RG int u, RG int ff){size[u] = 1, mx[u] = 0;for(RG int e = G2.first[u]; e != -1; e = G2.next[e]){RG int v = G2.to[e];if(vis[v] || v == ff) continue;GetRoot(v, u);size[u] += size[v];mx[u] = max(mx[u], size[v]);}mx[u] = max(mx[u], tot - size[u]);if(mx[u] < mx[root]) root = u;
}IL void GetDeep(RG int u, RG int ff, RG int dd, RG int nn){if(nn > k) return;S1[++S1[0]] = u, S2[++S2[0]] = u, deep[u] = dd, len[u] = nn;for(RG int e = G2.first[u]; e != -1; e = G2.next[e]){RG int v = G2.to[e], w = G2.w[e];if(vis[v] || v == ff) continue;GetDeep(v, u, dd + w, nn + 1);}
}IL void Solve(RG int u){vis[u] = 1, t[0] = 0, num[0] = 1;for(RG int e = G2.first[u]; e != -1; e = G2.next[e]){RG int v = G2.to[e];if(vis[v]) continue;GetDeep(v, u, G2.w[e], 1);for(RG int i = 1; i <= S1[0]; ++i){RG int dd = deep[S1[i]], nn = k - len[S1[i]];if(!num[nn]) continue;if(t[nn] + dd > ans1) ans1 = t[nn] + dd, ans2 = num[nn];else if(t[nn] + dd == ans1) ans2 += num[nn];}for(; S1[0]; --S1[0]){RG int dd = deep[S1[S1[0]]], nn = len[S1[S1[0]]];if(dd > t[nn]) t[nn] = dd, num[nn] = 1;else if(dd == t[nn]) num[nn]++;}}for(; S2[0]; --S2[0]){RG int dd = deep[S2[S2[0]]], nn = len[S2[S2[0]]];t[nn] = num[nn] = 0;}for(RG int e = G2.first[u]; e != -1; e = G2.next[e]){RG int v = G2.to[e];if(vis[v]) continue;root = 0, tot = size[v];GetRoot(v, u), Solve(root);}
}IL void SPFA(){Fill(dis, 127);Q.push(1), vis[1] = 1, dis[1] = 0;while(!Q.empty()){RG int u = Q.front(); Q.pop();for(RG int e = G1.first[u]; e != -1; e = G1.next[e]){RG int v = G1.to[e], w = G1.w[e];if(dis[u] + w < dis[v]){dis[v] = dis[u] + w;if(!vis[v]) vis[v] = 1, Q.push(v);}}vis[u] = 0;}
}IL void Build(){H.push(-1), Fill(vis, 0), vis[1] = 1;while(!H.empty()){RG int u = -H.top(); H.pop();for(RG int e = G1.first[u]; e != -1; e = G1.next[e]){RG int v = G1.to[e], w = G1.w[e];if(vis[v] || dis[v] != dis[u] + w) continue;G2.Add(u, v, w), G2.Add(v, u, w);vis[v] = 1, H.push(-v);}}
}int main(RG int argc, RG char* argv[]){tot = n = Input(), m = Input(), k = Input() - 1;G1.Init(), G2.Init();for(RG int i = 1; i <= m; ++i){RG int u = Input(), v = Input(), w = Input();G1.Add(u, v, w), G1.Add(v, u, w);}SPFA(), Build(), Fill(vis, 0);mx[0] = n + 1, GetRoot(1, 0),Solve(root);printf("%lld %lld\n", ans1, ans2);return 0;
}

转载于:https://www.cnblogs.com/cjoieryl/p/8473271.html

相关文章:

libevent源码深度剖析

原文地址&#xff1a;http://blog.csdn.net/sparkliang/article/details/4957667libevent源码深度剖析一——序幕张亮1 前言 Libevent是一个轻量级的开源高性能网络库&#xff0c;使用者众多&#xff0c;研究者更甚&#xff0c;相关文章也不少。写这一系列文章的用意在于&#…

元宇宙中可跨语种交流!Meta 发布新语音模型,支持128种语言无障碍对话

编译 | 禾木木出品 | AI科技大本营&#xff08;ID:rgznai100&#xff09;语言交流是人类互动一种自然的方式&#xff0c;随着语音技术的发展&#xff0c;我们可以与设备以及未来的虚拟世界进行互动&#xff0c;由此虚拟体验将于我们的现实世界融为一体。然而&#xff0c;语音技…

前端面试官,我为什么讨厌你。

近两年来&#xff0c;参加过的前端面试不下二十场了&#xff0c;吐槽一下。我所经历的&#xff0c;都是小公司&#xff0c;大公司的同学请无视。 招聘信息能否不要装逼&#xff1f;写一大堆你项目根本用不上的&#xff0c;来给谁看&#xff1f;我曾遇到上面写了一堆对js如何要求…

【ASP.NET Core】解决“The required antiforgery cookie xxx is not present”的错误

当你在页面上用 form post 内容时&#xff0c;可能会遇到以下异常&#xff1a; The required antiforgery cookie "????????" is not present. 咱们来重现一下错误。新建一个 ASP.NET Core 项目&#xff0c;模板选【空】就行了&#xff0c;这是老周最喜欢的项…

linux系统级别的能够打开的文件句柄的数file-max命令

简单的说, max-file表示系统级别的能够打开的文件句柄的数量, 而ulimit -n控制进程级别能够打开的文件句柄的数量.man 5 proc, 找到file-max的解释&#xff1a;file-max中指定了系统范围内所有进程可打开的文件句柄的数量限制(系统级别, kernel-level). &#xff08;The value …

这封以数字构写的蓝图,正在实现笔尖所触即世界

作者 | 贾凯强出品 | AI科技大本营&#xff08;ID:rgznai100&#xff09;一撇一捺&#xff0c;一勾一抹&#xff0c;笔走龙蛇&#xff0c;可见真意。笔者小时候字迹潦草&#xff0c;便总是抱怨为什么一定要写字好看&#xff1f;而如今计算机统治了世界&#xff0c;键盘和鼠标早…

Svn 笔记—— Hooks

pre-commit 钩子功能&#xff1a;[rootDa hooks]# cat /application/svndata/sadoc/hooks/pre-commit#!/bin/bash#Check message lenth ---更新版本时强制输入信息小于5个字符会退出REPOS"$1"TXN"$2"logmsgsvnlook log -t $TXN $REPOS |grep &q…

22.CSS边框与背景【上】

第十七章 CSS边框与背景【上】 一、声明边框 属性 值 说明 CSS版本 1、border-width 长度值 设置边框的宽度&#xff08;可选&#xff09; 1 2、border-style 样式名称 设置边框的样式&#xff08;必选&…

一致性 hash 算法( consistent hashing )

原文地址&#xff1a;http://blog.csdn.net/sparkliang/article/details/5279393consistent hashing 算法早在 1997 年就在论文 Consistent hashing and random trees 中被提出&#xff0c;目前在 cache 系统中应用越来越广泛&#xff1b; 1 基本场景 比如你有 N 个 cache 服务…

【json的使用】

1、json格式字符串&#xff1a;Java代码/** 操作成功 200 */ public static final String RESULT_SUCCESS "{\"code\":\"200\",\"message\":\"成功!\"}";复制代码2、解析json字符串&#xff1a;Java代码JSONObject object…

通过 for 循环,比较 Python 与 Ruby 编程思想的差别

作者 | Doug Turnbull译者 | 豌豆花下猫Python猫来源 | Python猫Ruby 与 Python 之间的差异在很大程度上可通过for循环看出本质。Python 拥有for语句。对象告诉for如何进行协作&#xff0c;而for的循环体会处理对象返回的内容。Ruby 则相反。在 Ruby 中&#xff0c;for本身&…

Blippar放大招,要开源其AR和计算机视觉技术

AR公司Blippar将向第三方开发者提供AR和计算机视觉技术API&#xff0c;来推动他们的AR商业应用解决方案的发展。 致力于用AR技术帮助一些大品牌进行品牌故事和消费者营销的AR公司Blippar&#xff0c;最近对外宣布&#xff0c;要将他们的AR和计算机视觉技术API&#xff0c;提供…

Linux CPU数量判断命令

其实只要 #include <unistd.h>long num sysconf(_SC_NPROCESSORS_ONLN); 便可以获得当前CPU的数量。。。 判断依据&#xff1a;1.具有相同core id的cpu是同一个core的超线程。2.具有相同physical id的cpu是同一颗cpu封装的线程或者cores。 英文版&#xff1a;1.Physical…

5月.CN域名注册量持续上涨至1199万个 净增14万

IDC评述网&#xff08;idcps.com&#xff09;06月11日报道&#xff1a;根据中国互联网络信息中心&#xff08;CNNIC&#xff09;最新公布的数据显示&#xff0c;在5月份&#xff0c;.CN域名总量持续增至11,990,264个&#xff0c;环比上月&#xff0c;净增143,346个&#xff0c;…

人工智能/云原生/数据科学/计算等方向内容整理志愿者招募了!

持续招募内容整理志愿者&#xff01;云原生、数据科学、AI、低代码、计算等方向&#xff0c;有意愿的小伙伴&#xff0c;欢迎识别二维码提前报名哦。我们将持续为爱学习、有时间的小伙伴&#xff0c;提供多重福利&#xff01;要求&#xff1a;1. 你需要具备一定学术背景&#x…

三个轻量级WebServer--lighttpd,thttpd,shttpd介绍

国内绝大部分的web server不是IIS就是Apache&#xff0c;而论市场占有率&#xff0c;我认为Apache是大赢家了&#xff0c;至少是占据了半壁江山。但除了IIS/Apache外&#xff0c;其实我们有很多选择&#xff0c;对于高负载/大并发的网站而言&#xff0c;高性能、轻量级的web se…

实验四 主存空间的分配和回收

实验四 主存空间的分配和回收 一、目的和要求 1.1. 实验目的 用高级语言完成一个主存空间的分配和回收程序&#xff0c;以加深对动态分区分配方式及其算法的理解。 1.2. 实验要求 采用连续分配方式之动态分区分配存储管理&#xff0c;使用首次适应算法、循环首次适应算法、最佳…

技术“摸鱼” 大神,国外小哥 5 年白拿 45 万工资!

整理 | 孙胜出品 | CSDN&#xff08;ID&#xff1a;CSDNnews&#xff09;自从2017年谷歌旗下的AlphaGo以3比0战胜柯洁后&#xff0c;“人工智能即将取代人类工作”一度成为人们热议的话题。然而最近一位国外小哥用他亲身经历告诉我们&#xff0c;虽然程序终将代替人类执行重复劳…

Python杂篇

一&#xff1a;文件保存 def save_to_file(file_name, contents):fh open(file_name, w)fh.write(contents)fh.close()save_to_file(mobiles.txt, your contents str)结果&#xff1a; 将字符串修改则覆盖原来的字符串 将字符串用变量替代 将 fh open(file_name, w)写的权限去…

整理了 70 个 Python 面向对象编程案例,怎能不收藏?

作者 | 周萝卜来源 | 萝卜大杂烩Python 作为一门面向对象编程语言&#xff0c;常用的面向对象知识怎么能不清楚呢&#xff0c;今天就来分享一波文章很长&#xff0c;高低要忍一下&#xff0c;如果忍不了&#xff0c;那就收藏吧&#xff0c;总会用到的在 Python 中创建一个类及其…

ionic中的ion-option-button

2019独角兽企业重金招聘Python工程师标准>>> 代码 <ion-option-button class"button-assertive" ng-click"df(itemData)">批准 </ion-option-button> 效果图 转载于:https://my.oschina.net/u/1416844/blog/465730

memset函数详细说明

1。void *memset(void *s,int c,size_t n)总的作用&#xff1a;将已开辟内存空间 s 的首 n 个字节的值设为值 c。2。例子#include <stdio.h>#include <string.h>void main(){char s[]"hello";memset(s,*,2);printf("%s",s);} 输出&#xff1a…

CES Asia专题|微鹅展示无线充电,智能手机的无线充电时代何时来临?

无线充电离商业化应用还有多远&#xff1f; 此前一直有传闻苹果在新一代iPhone上会推出无线充电&#xff0c;在CES Asia上&#xff0c;我们也看到了无线充电技术方案解决商微鹅带来的最新产品。 据了解&#xff0c;目前我们所说的无线充电其实是指近场无线充电&#xff0c;让充…

Linux下Socket编程

Linux下Socket编程 网络的Socket数据传输是一种特殊的I/O&#xff0c;Socket也是一种文件描述符。Socket也具有一个类似于打开文件的函数调用Socket()&#xff0c;该函数返回一个整型的Socket描述符&#xff0c;随后的连接建立、数据传输等操作都是通过该Socket实现的。 什么…

看大众点评如何通过实时监控系统CAT打造7*24服务

为什么80%的码农都做不了架构师&#xff1f;>>> 看大众点评如何通过实时监控系统CAT打造7*24服务 2015-06-08 尤勇 高可用架构 https://github.com/dianping/cat 本文根据尤勇在【QCon高可用架构群】中的分享内容整理而成。 尤勇是大众点评网资深工程师&#x…

Python 快速实现分列转到行!

作者 | 黄伟呢来源 | 数据分析与统计学之美之前看到一篇文章&#xff0c;用Excel快速实现分列转到行的操做。数据源大致是这样的&#xff1a;基于此&#xff0c;我动起了一个念头&#xff1a;看看如何用Python快速实现这个操作。数据源已经构造好&#xff0c;咱们开干&#xff…

javabean属性的类型选择包装类还是基本数据类型

学生 参加考试&#xff0c;需要在表中存放分数score字段 &#xff0c;score是采用double 还是Double &#xff1f; 假如有个同学张三 没有参加考试&#xff0c;double 默认值 0 &#xff0c; Double 默认值 null 使用原始类型&#xff0c;无法区分0值没有数据&#xff0c;还是值…

C语言实现的Web服务器

另一篇&#xff1a;标准C实现WEB服务器http://blog.sina.com.cn/s/blog_4b73e7600100b02c.html本文原文地址&#xff1a; http://blog.sina.com.cn/s/blog_4b73e760010007id.html自己研究了好几天终于写出来一个&#xff0c;哈哈&#xff0c;当然也从网上得到了很多的帮助拉。谢…

使用深度学习检测混凝土结构中的表面裂缝

作者 | 小白来源 | 小白学视觉混凝土建筑裂缝介绍表面裂缝检测是监测混凝土结构健康的一项重要任务。如果裂纹发展并继续扩展&#xff0c;它们会减少有效承载表面积&#xff0c;并且随着时间的推移会导致结构失效。裂纹检测的人工过程费时费力&#xff0c;且受检验人员主观判断…