UVA11022 String Factoring

简要题意

给出一个字符串 \(S\),你可以进行任意次(压缩)操作,每次操作可以把字符串中连续几个相同的部分压缩成相同的一个。操作可以嵌套进行。你需要求出操作后字符串的最小长度。

多组数据。以 * 结束。

\(1 \leq |S| \leq 80\)\(S\) 中仅包含英文大写字母。

思路

这道题直接用 KMP 不太好做,我们发现一个区间的答案可以由它的子区间合并得到。于是我们可以考虑区间 DP。

\(f_{i,j}\) 为区间 \([i,j]\) 的答案。

显然有 \(f_{i,i}=1\)

则对于一个不由几个相同部分组成的区间可以枚举断点简单转移得到:

\[f_{i,j}=\min_{k=i}^{j-1}{f_{i,k}+f_{k+1,j}} \]

然后考虑可以压缩的区间。除了上述转移外还有额外的转移。我们令最小重复部分长度(压缩后的长度)为 \(L\)。则额外转移为:

\[f_{i,j}=\min(f_{i,j},f_{i,j+L-1}) \]

然后考虑如何求 \(L\)。我们先求出 \([i,j]\) 之间的字符串的失配数组 \(\operatorname{fail}\)。如果 \((j-i+1) \bmod ((j-i+1)-\operatorname{fail}({j})) = 0\) 则代表可以压缩。然后 \((j-i+1)-\operatorname{fail}({j})\) 就是 \(L\) 了。至于严谨推导过程,见 OI Wiki。时间复杂度为 \(O(n)\)

然后这道题我们就可以做到 \(O(n^3)\) 了。(据说暴力求 \(L\) 也可以过)

最后贴一下完整的转移方程(如果 LaTex 炸了可以去上面的链接里查看):

\[f_{i,j}=\begin{cases} &1&i=j\\ &\min(\min_{k=i}^{j-1}{(f_{i,k}+f_{k+1,j})},\begin{cases} &f_{i,j+(j-i+1)-\operatorname{fail}({j})-1}&(j-i+1) \bmod ((j-i+1)-\operatorname{fail}({j})) = 0\\ &\infty&\text{otherwise} \end{cases})&\text{otherwise}\\ \end{cases} \]

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

int f[85][85],fail[85];
bool vis[85][85];
string str;
int n;

int dp(int l,int r){
    if(vis[l][r]) return f[l][r];
    vis[l][r]=1;
    if(l==r) return f[l][r]=1;
    f[l][r]=INT_MAX;
    for(int i=l;i<r;i++){
        f[l][r]=min(f[l][r],dp(l,i)+dp(i+1,r));
    }
    for(int i=1;i<=n;i++) fail[i]=0;
    for(int i=l+1,j;i<=r;i++){
        j=fail[i-1];
        while(j&&str[l+j]!=str[i]) j=fail[l+j-1];
        if(str[l+j]==str[i]) j++;
        fail[i]=j;
    }
    if((r-l+1)%(r-l+1-fail[r]) == 0){
        f[l][r]=min(f[l][r],dp(l,l+(r-l+1-fail[r])-1));
    }
    return f[l][r];
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    while(cin>>str){
        if(str[0] == '*') break;
        memset(vis,0,sizeof(vis));
        n=str.size();str=" "+str;
        cout<<dp(1,n)<<'\n';
    }
    return 0;
}
如果文章有问题,静待斧正,建议向我(@xiezheyuan)发送洛谷私信并指出博文地址 http://www.cnblogs.com/zheyuanxie/p/uva11022.html !
本文转载于网络 如有侵权请联系删除

相关文章

  • rsa 详解及例题及python

    rsa详解及例题及python文章目录rsa详解及例题及python算法原理算法描述案例手稿实现python运算m=71->c=15c=15->m=71正常的rsac->mm->c安全性运算速度算法原理RSA公开密钥密码体制的原理是:根据数论,寻求两个大素数比较简单,而将它们的乘积进行因式分解却极其困难,因此可以将乘积公开作为加密密钥算法描述任意选取两个不同的大素数p和q计算乘积n=pqn的欧拉函数φ(n):φ(n)=(p-1)(q-1)任意选取一个大整数e,满足gcd(e,φ(n))=1,整数e用做加密钥(注意:gcd是最大公约数,e的选取是很容易的,例如,所有大于p和q的素数都可用)确定的解密钥d,满足(de)modφ(n)=1公开整数n和e,秘密保存d公钥(n,e)私钥(n,d)c:密文 m:明文将明文m加密成密文c:c=m^emodn 将密文c解密为明文m:m=c^dmodn案例手稿我可是开了计算器的,这手算不来????,数据真实有效实现python运算数据同手稿最后一个 m=71->c=15importgmpy2 e=13 p=7 q=11

  • 搞清楚系统到底怎样支撑高并发以及架构图的绘制(面试向)

        大多数人面试的时候经常会被问到:你简历上有高负载高并发的经验,那到底你的系统是怎样设计的?    如果没有过相关的项目经验,大多数同学被问到这个问题压根儿没什么思路去回答,不知道从什么地方说起,其实,就算没有相关的经验,只要事先编好话术,搞清楚架构图,回答此类问题也还是可以滴水不漏的。     首先,在脑子里虚拟一个大用户量背景下的场景,如果我们手头有几台4核8g的服务器,假设一个平台用户量是500万。此时日活用户是50万,日访问量在600-700万左右,高峰期对系统每秒请求是500/s。然后对数据库的每秒请求数量是1500/s,这个时候会怎么样呢?如果系统内处理的是较为复杂的一些业务逻辑,是那种重业务逻辑的系统的话,是比较耗费CPU的。此时,4核8G的机器每秒请求达到500/s的时候,很可能你的机器CPU负载较高了。然后数据库层面,以上述的配置而言,其实基本上1500/s的高峰请求压力的话,还算可以接受。这个主要是要观察数据库所在机器的磁盘负载、网络负载、CPU负载、内存负载,按照我们的线上经验而言,那个配置的数据库在1500/s请求压力下是没问题的。所以此时需要做的一个事

  • ping命令网络抓包分析

    首先,执行ipconfig确认自己电脑的ip地址可以得到我的电脑的ip地址为192.168.43.15,网关地址为192.168.43.1打开[wireshark]抓包工具,ping网关,看看会发生什么[命令行]中,我们发送了4个具有32B的数据,从抓包工具中,我们可以看出该命令采用的是icmp协议第1帧该帧序号为1,发生在第0.00s,源地址为192.168.43.15(本机),目标地址为192.168.43.1(网关),协议为ICMP协议,长度为74B,信息:Echo(ping)requestid=0x0001,seq=11/2816,ttl=128(replyin2)从图中可以看出,该层一共40B,其中控制信息8B,数据信息32B,第一个控制信息Type字段占1B,表示类型,8代表请求类型,0代表回复类型Code字段占1B,暂不清楚作用。Checksum字段,占2B,用来校验该层数据是否正确,该帧中ChecksumStatus为good,表示该帧未发生错误,为正常帧。标识符字段,占2B,该帧为0x0001(0x0100是什么?)sequence序列号字段,占2B,该帧为0x000

  • Leetcode|887. 鸡蛋掉落(动规找最优BST根节点 + 将解作为状态)

    文章目录1动态规划(递归超时)2动态规划(二分搜索优化,5%beat,1400ms)3动态规划(将解作为状态,100%beat,0ms)致谢1动态规划(递归超时) 【状态】:①第i层扔碎了;②第i层扔没碎【dp函数含义】:剩余k个鸡蛋,有n层楼时,最坏情况下最少扔鸡蛋的次数为dp(k,n)【初始化】:状态有两个,因此需分别初始化,当楼层为0时,最少扔蛋次数为0;当剩余鸡蛋仅1个时,需做线性扫描,因此最坏情况下最少扔蛋次数为n【状态转移】minCont表示N课BST树中最小深度BST树的深度值(在N个点中找最佳切分点)minCont=min[minCont,max(第i棵BST左分支depth,第i棵BST右分支depth)+1(root)]【记录重叠子问题】:需要用到map类数据结构,由于key=(k,n),C++中可以使用tuple来绑定多key(比pair方便),但只有底层红黑树实现的map可以将tuple作为key,底层哈希表实现的unordered_map不可以,原因很简单,没有多key对应的哈希映射,需要自己手动实现.classSolution{ private: //dp备

  • http视频文件传输(http 206)

    http206http协议通过206实现断点续传,上传下载,以及video标签的是文件播放requestHttp部分内容请求头部需要指定:Range:bytes=0- 服务端,解析range范围,读取文件指定位置的数据,获取video视频video标签会显示视频发送3个request,range(0-)和range(视频结尾信息段-),request视频文件头部后面的数据(一小段) 如果发过去的视频无显示,可以查看range的范围是否正确,range索引(0,filelen-1),如果操作文件索引最大值,可能出现视频无显示的情况 responseHttp响应需要指定响应头:content-range:bytes:0-、httpcode为206 dotnetcore异步写文件的方式返回整个文件,可以在远端电脑查看大文件,Response.ContentType="video/mp4"; Response.Headers["Cache-Control"]="no-cache"; Response.StatusCode=(int)H

  • Ubuntu16.04 下编译安装tesseract 4.00.00alpha 及测试

    3.05.01及以后的版本没有Linux的二进制包,需要编译安装.#安装相关组件 sudoapt-getinstallg++#orclang++(presumably) sudoapt-getinstallautoconfautomakelibtool sudoapt-getinstallautoconf-archive sudoapt-getinstallpkg-config sudoapt-getinstalllibpng12-dev sudoapt-getinstalllibjpeg8-dev sudoapt-getinstalllibtiff5-dev sudoapt-getinstallzlib1g-dev sudoapt-getinstalllibicu-dev sudoapt-getinstalllibpango1.0-dev sudoapt-getinstalllibcairo2-dev复制依赖图像库Leptonica,在编译tesseract前先编译Leptonica,版本对应关系见Compiling#linux,3.05对应leptonica-1.74.tar.gz

  • 腾讯云国产数据库TBase在保险行业的应用实践

    本文是腾讯云高级工程师李巍在腾讯云Techo开发者大会现场的演讲实录,演讲主题是《腾讯自研HTAP数据库TBase的应用实践》。今天给大家分享的主要内容包括两部分: TBase概述;TBase在保险公司的应用实践。李巍演讲现场搜索关注“腾讯云数据库”官方微信,回复“1106李巍”即可下载本视频演讲PPT。TBase概述TBase是腾讯自主研发的新一代分布式NewSQL国产数据库,具备业界领先的HTAP能力,在提供NewSQL便利性的同时还能完整支持事务并保持SQL兼容性,现已开源,详情请点击☞微信支付用的数据库开源了首先我们来看看TBase的发展历程,TBase是从社区的PostgreSQL发展而来,最早就是替换Oracle的部分场景,发展到今天成为一个功能完备的企业级分布式HTAP数据库。从2011年到现在,八年的时间TBase走过了3个时代。2011-2013单机时代,作为离线的TDW大数据平台的一个互补,提供小数据量的实时展示。最重要的特性就是跟大数据平台互联互通。 2013-2016OLTP时代,随着业务发展单机计算瓶颈逐渐凸显,促使我们进行集群化,早期集群化的过程主要是侧重O

  • 一文读懂「中台」的前世今生

    导读:中台,通过业务、数据和技术的抽象,形成了服务能力的复用,构建了企业级的服务能力,消除了企业内部各业务部门、各分子公司间的壁垒,适应了企业,特别是大型企业集团业务多元化的发展战略。基于中台,可快速构建面向最终消费者和客户的前台应用,从而满足各种个性化特征的前台需求,为企业的数字化转型提供一条明确的道路。作者:陈新宇罗家鹰邓通江威如需转载请联系大数据(ID:hzdashuju)01什么是中台那么中台到底是什么?中台是一个新的概念,还是旧有名词,在新时期我们赋予其新的内涵?本节介绍中台的历史起源,以及数字化时代中台在企业信息化建设中的展现和作用。1.中台的源起中台不是一个新名词。在一个投资银行的组织结构中:前台(Frontoffice)是与客户和顾客(无论是个人客户还是公司客户)直接互动的岗位,诸如大堂经理、客户经理、柜员等。中台(Middleoffice)是指直接支援前台工作的所有人员,使用前台或后台的资源,为前台提供专业性的管理和指导,并进行风险控制,比如风险管理、合规、财务管控以及IT服务等。后台(Backoffice)指幕后的职能岗位,行使管理职能,比如结算、清算、会计、人力资

  • Fiori Launchpad Tile点击后跳转的调试技巧

    在SAPFiorilaunchpad里点击某个tile之后,后台会计算出跳转的目标url返回给前台。下图中一个个白色的方框就成为tile。每个tile点击之后,会打开一个对应的Fiori应用。本文介绍如何在后台调试这个跳转目标的计算逻辑。首先我们可以直接在浏览器里点击tile或者用Postman手动触发这个跳转目标的url解析请求:在后台使用事务码SICF,在该icfnode的handlerclass的HANDLE_REQUEST里设置断点:在Postman里触发请求,断点触发,在第61行里从Fiori的前台系统执行进入Fiori后台系统的执行。关于Fiori前后台系统的区分,参考我的微信公众号文章SAPFiori应用的三种部署方式后台执行逻辑:首先拿元数据metadata再取实际数据。下图是数据请求正文:得到action名称:然后根据action名称调用对应的处理逻辑:首先从cache里读取:cache没命中:于是去数据库取:得到结果。下图解析的结果SAPUI5.Component=后面的字符串cus.crm.mycalendar就是tile点击之后待打开的Fiori应用。字段URL

  • OpenGL ES——着色器

    前言在App开发中,为了追求给CPU减负,我们经常会使用GPU来渲染我们想要显示的图片。如何控制GPU为我们工作?渲染管线GPU的工作流程是固定的:image.png上图就是OpenGLES2.0的图形管线。图中阴影部分的VertexShader和FragmentShader是可编程管线。可编程管线就是说这个操作可以动态编程实现而不必固定写死在代码中。可动态编程实现这一功能一般都是脚本提供的,在OpenGLES中也一样,编写这样脚本的能力是由着色语言(ShaderLanguage)提供的。着色器一个Shader就像一个函数,我们需要定义它的输入和输出。然后对输入和输出做一系列转换。OpenGL的优势就在于让这一系列转化在GPU上完成。privatestaticfinalStringVERTEX_SHADER= "attributevec4a_position;\n"+ "attributevec2a_texcoord;\n"+ "varyingvec2v_colorcoord;\n"+ "voidmain(){\n&

  • 洛谷P3388 【模板】割点(割顶)(tarjan求割点)

    题目背景割点题目描述给出一个n个点,m条边的无向图,求图的割点。输入输出格式输入格式:第一行输入n,m下面m行每行输入x,y表示x到y有一条边输出格式:第一行输出割点个数第二行按照节点编号从小到大输出节点,用空格隔开输入输出样例输入样例#167 12 13 14 25 35 45 56复制输出样例#1:1 5复制说明n,m均为100000tarjan图不一定联通!!!tarjan求割点,若low[v]>=dfn[u],说明从v不能走回u之前的点那么u一定能将v与之前的点分割开根节点需要特判,只有多于两个孩子时才是割点//luogu-judger-enable-o2 #include<cstdio> #include<cstring> #include<algorithm> #definegetchar()(S==T&&(T=(S=BB)+fread(BB,1,1<<15,stdin),S==T)?EOF:*S++) charBB[1<<15],*S=BB,*T=BB; usingnamespacestd;

  • 【机器学习实战】第3章 决策树

    第3章决策树<scripttype="text/javascript"src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=default"></script>决策树概述决策树(DecisionTree)算法主要用来处理分类问题,是最经常使用的数据挖掘算法之一。决策树场景一个叫做"二十个问题"的游戏,游戏的规则很简单:参与游戏的一方在脑海中想某个事物,其他参与者向他提问,只允许提20个问题,问题的答案也只能用对或错回答。问问题的人通过推断分解,逐步缩小待猜测事物的范围,最后得到游戏的答案。一个邮件分类系统,大致工作流程如下:首先检测发送邮件域名地址。如果地址为myEmployer.com,则将其放在分类"无聊时需要阅读的邮件"中。 如果邮件不是来自这个域名,则检测邮件内容里是否包含单词"曲棍球",如果包含则将邮件归类到"需要及时处理的朋友邮件", 如果不包含则将邮件归类到&qu

  • Go的50坑:新Golang开发者要注意的陷阱、技巧和常见错误[1]

    Go是一门简单有趣的语言,但与其他语言类似,它会有一些技巧。。。这些技巧的绝大部分并不是Go的缺陷造成的。如果你以前使用的是其他语言,那么这其中的有些错误就是很自然的陷阱。其它的是由错误的假设和缺少细节造成的。 如果你花时间学习这门语言,阅读官方说明、wiki、邮件列表讨论、大量的优秀博文和RobPike的展示,以及源代码,这些技巧中的绝大多数都是显而易见的。尽管不是每个人都是以这种方式开始学习的,但也没关系。如果你是Go语言新人,那么这里的信息将会节约你大量的调试代码的时间。 目录 初级篇 开大括号不能放在单独的一行 未使用的变量 未使用的Imports 简式的变量声明仅可以在函数内部使用 使用简式声明重复声明变量 偶然的变量隐藏AccidentalVariableShadowing 不使用显式类型,无法使用“nil”来初始化变量 使用“nil”SlicesandMaps Map的容量 字符串不会为“nil” Array函数的参数 在Slice和Array使用“range”语句时的出现的不希望得到的值 Slices和Arrays

  • WCF初探-10:WCF客户端调用服务

    创建WCF 服务客户端应用程序需要执行下列步骤:   获取服务终结点的服务协定、绑定以及地址信息 使用该信息创建WCF客户端 调用操作 关闭该WCF客户端对象   WCF客户端调用服务存在以下特点:   服务和客户端使用托管属性、接口和方法对协定进行建模。若要连接客户端应用程序中的服务,则需要获取该服务协定的类型信息。通常,我们使用Svcutil.exe(ServiceModelMetadataUtilityTool)来完成,也可以直接在客户端项目上引用服务地址完成。它们会从服务中下载元数据,并使用您选择的语言将其转换到托管源代码文件中,同时还创建一个您可用于配置WCF客户端对象的客户端应用程序配置文件 WCF客户端是表示某一个WCF服务的一个本地对象,客户端可以使用这种形式与远程服务进行通信。WCF客户端类型可以实现目标服务协定,因此当您创建一个服务协定,并对其进行配置后,就可以直接使用客户端对象调用服务操作。WCF运行时将方法调用转换为消息,然后将这些消息发送到服务,侦听回复,并将这些值作为返回值或out参数(或ref参数)返回到WCF

  • 面试:计算机网络基础详解(一)

    计算机网络是计算机、软工类面试的基础,不管是软件/硬件开发、技术支持还是测试职位,都会涉及到计算机网络的基础知识,本文基于笔者之前的面试准备所做的相关知识整理。本文的主要内容: OSI与TCP/IP模型 OSI七层模型 OSI的缺陷 TCP/IP五层模型 TCP三次握手和四次挥手 TCP建立连接 TCP三次握手,如果两次握手会怎么样? TCP关闭连接 为什么建立连接是三次握手,而关闭连接却是四次挥手呢? 为什么需要TIME_WAIT状态? TCP协议如何保证可靠传输 HTTP和HTTPS 基本概念 HTTPS和HTTP的区别 HTTP响应的状态码 HTTP长连接、短连接 OSI与TCP/IP模型 OSI七层模型 OSI(OpenSystemInterconnect),即开放式系统互联。一般都叫OSI参考模型,是ISO(国际标准化组织)组织在1985年研究的网络互连模型。 OSI定义了网络互连的七层框架(物理层、数据链路层、网络层、传输层、会话层、表示层、应用层),即ISO开放互连系统参考模型。     从上到下介绍每层的功能: 应用层:OS

  • 途家网 BI 总监分享:如何搭建一个数据分析团队

    以前说到数据驱动业务增长,我们第一个想到的可能是数据分析的方法。但就目前来看,数据驱动业务的增长已经成为一个不仅仅是分析方法和模型,而是包括了数据人才培养、数据架构的设计,甚至整个公司组织架构设计的企业治理问题。所以,今天我想从途家数据团队的发展、部门的构成及职责这两个方面去跟大家分享一下途家网的一些实践。 如果对一个公司的业务没有足够的了解,是没有办法去做分析的,今天演讲中阐述的不管是组织架构的设计还是分析案例,都是紧紧围绕途家网的商业模型展开,所以我先大概介绍一下途家的业务:途家网是一家已经进入“独角兽”俱乐部的全球公寓民宿预订平台,于2011年12月1日正式上线。我们提供服务公寓、度假公寓、别墅、客栈、民宿等各类度假租赁产品的在线搜索、查询和交易服务。 一、数据分析团队发展的5个阶段 我们途家网成立五年以来,整个数据团队的成长也是经历了五个阶段。 途家网数据团队的发展线路图 第一阶段:从2011年底途家网正式上线到2013年2月,这个阶段我们没有专业的数据分析师。 在公司刚刚成立的阶段,没有招专业数据分析师的必要,但是这个时候仍然需要做数据分析。途家网的创始人具备深厚的计算机背

  • 开发 Sublime Text 3 插件简易教程

    之前我常用的编程工具是UltraEdit和Editplus,UltraEdit里强大的搜索和大文本加载功能是我喜欢的。但这两款文本编辑器是收费的,我一直用破解版的心里有鬼。自从发现了SublimeText这款免费编辑器后,它就成了我爱不释手的优先选择的编程工具。SublimeText强大的语法自动提示功能是我最看重的一点,我经常会编辑一些HTML代码,HTML代码里的所有语法标记,它都能提供自动补全,还能提示所有CSS属性的可选属性值,极大的方便了HTML和CSS开发。 SublimeText提供了非常自由的插件(plugins)扩展功能。我最近出现了一个小小的需求,想开发出一个简单的扩展功能。我想在SublimeText的系统菜单里添加一个新的菜单,叫做“HTML尖括号转换”,但当点击它后,编辑器里HTML文本中的所有尖括号(>和<)都将会转换成&gt;和&lt;。WEB程序员应该知道这个功能的用武之地。 开发这个插件非常的简单。只需要几行代码。但更复杂的插件也都是这种简单插件基础上扩展出来的。下面我将要介绍开发这个插件需要的步骤和方法。 首先,你需要懂一

  • 欧拉函数

    原博客:https://blog.csdn.net/zxwsbg/article/details/81488956 φ(n)=n*(1-1/p1)*(1-1/p2)*(1-1/p3)*(1-1/p4)…..(1-1/pn),其中pi为n的质因数 方法1:求单个数的欧拉函数 1longlongeular(longlongn){ 2longlongans=n; 3for(inti=2;i*i<=n;i++){ 4if(n%i==0){ 5ans-=ans/i;//等价于通项,把n乘进去 6while(n%i==0)//确保下一个i是n的素因数 7n/=i; 8} 9} 10if(n>1)ans-=ans/n; 11//最后可能还剩下一个素因数没有除 12returnans; 13}复制 ViewCode 方法2:打表求欧拉函数 1voideuler(){ 2for(inti=2;i<maxn;i++){ 3if(!phi[i])for(intj=i;j<maxn;j+=i){ 4if(!phi[j])phi[j]=j; 5phi[j]=phi[j]/i*(

  • 浏览器缓存

    转载自 https://juejin.im/post/5c93ba526fb9a070ca103898   强制缓存和对比缓存 两类缓存规则可以同时存在,强制缓存优先级高于对比缓存,也就是说,当执行强制缓存的规则时,如果缓存生效,直接使用缓存,不再执行对比缓存规则。 (1)Cache-Control:no-cache 使用no-cache指令的目的是为了防止从缓存中返回过期的资源。客户端发送的请求中如果包含no-cache指令,则表示客户端将不会接收缓存的资源。每次请求都是从服务器获取资源,返回304。   (2)Cache-Control:no-store 使用no-store指令表示请求的资源不会被缓存,下次任何其它请求获取该资源,还是会从服务器获取,返回200,即资源本身。 Cache-Control作为响应头字段 Cache-Control:public 当指定使用public指令时,则明确表明其他用户也可利用缓存。 Cache-Control:private 当指定private指令后,响应只以特定的用户作为对象,这与public指令的行为相

  • 单链表操作

    单链表的基本操作 /* 单链表分两种:有头结点和无头结点 插入单链表方式:头部插入和尾部插入,不管是头部插入还是尾部插入,步骤是: 1)先把新结点的next指针指向下一个结点 2)再把前一个结点的next指向新结点 */ #include<stdio.h> #include<stdlib.h> //单向链表数据结构 typedefstructLinkedList{ intdata; structLinkedList*next; }LinkedList; //初始化一个单链表 //头部插入结点 LinkedList*link_list_create_from_head(int*data,intlength) { //创建头结点(相当于哨兵结点,不存储数据)并分配空间 LinkedList*head=(LinkedList*)malloc(sizeof(LinkedList)); if(head==NULL) { printf("申请空间失败"); returnNULL; } //初始化链表为空链表 head->next=NULL; for(inti

  • Kruskal重构树

    Kruskal重构树 前置知识:Kruskal算法,LCA 最近刚学,如有错误欢迎提出。 对图建Kruskal重构树的主要作用:求原图中两个点所在路径上的最长边的最小值或最短边的最大值。 如何建Kruskal重构树 在Kruskal的基础上,当两个点x,y不再一个并查集中,那么我们就再引入一个新的点,这个点的权值是x,y两点再原图中的边的权值。最后把两个并查集的根节点指向新的点。 (下图中右边是左边图建立的Kruskal重构树) 首先是连4和6两个点,引入一个新点7,连边4和7以及6和7,其权值是2 然后连3和4这一条边,引入一个新点8,连3和4所在的并查集的根节点7,权值为3. 后面和前面一样,和kruskal算法过程差不多。 为什么能算出来呢? 首先如果要求两点路径最长边的最小值。我们需要按照边权从小到大去建kruskal重构树,注意所有新点表示的其实是一条边,这时只有x,y两点lca这个点连边x和y才能联通,那么才能有一条路径使x,y相连,由于从小到大连边,那么最后连的lca表示的这条边一定是路径中的最大边, 又因为后面连的边都比lca表示的边大,后面出现的x,y之间的边的

相关推荐

推荐阅读