wxyww

分类

未归档(12) 精品(28) 题解(65)

/ 注册

全部文章（共395篇）

网络流24题——试题库问题

题目链接：luogu2763 题目描述 «问题描述：假设一个试题库中有n道试题。每道试题都标明了所属类别。同一道题可能有多个类别属性。现要从题库中抽取m 道题组成试卷。并要求试卷包含指定类型的试题。试设计一个满足要求的组卷算法。 «编程任务：对于给定的组卷要求，计算满足要求的组卷方案。...

2018-07-23

0 395

费用流的简单应用

题目链接：luogu4013 题目：给定一个由 n 行数字组成的数字梯形如下图所示。梯形的第一行有 m 个数字。从梯形的顶部的 m 个数字开始，在每个数字处可以沿左下或右下方向移动，形成一条从梯形的顶至底的路径。分别遵守以下规则：从梯形的顶至底的 m 条路径...

2018-07-20

0 401

费用流的简单应用

题目链接：luogu4013 题目：给定一个由 n 行数字组成的数字梯形如下图所示。梯形的第一行有 m 个数字。从梯形的顶部的 m 个数字开始，在每个数字处可以沿左下或右下方向移动，形成一条从梯形的顶至底的路径。分别遵守以下规则：从梯形的顶至底的 m 条路径...

2018-07-20

0 458

Manacher算法

Manacher算法？？？　　Mancher算法是用来找最大回文串的，因为功能太过单一，所以用处不是很多，但是在找回文串方面还是很强大的。大致原理：　　枚举回文串的中点，用p[i]表示以i为中心的最大回文串的长度。然后对p[i]进行扩展就可以了。　　　　最简单的扩展就是当s[i+p[...

字符串

2018-07-18

0 471

Manacher算法

Manacher算法？？？　　Mancher算法是用来找最大回文串的，因为功能太过单一，所以用处不是很多，但是在找回文串方面还是很强大的。大致原理：　　枚举回文串的中点，用p[i]表示以i为中心的最大回文串的长度。然后对p[i]进行扩展就可以了。　　　　最简单的扩展就是当s[i+p[...

字符串

2018-07-18

0 468

KMP算法

KMP算法？？？　　kmp算法最简单的就是用来匹配子串，也就是从字符串s1中找到s2出现的次数与位置。同时，kmp的nxt数组还有很多高能的用处。 NXT数组：　　nxt数组是kmp算法中极其重要的部分，nxt[i]表示子串s中，上一次s[i]为后缀的位置。（看了后面的原理就很明白了） ...

字符串

2018-07-18

0 430

KMP算法

KMP算法？？？　　kmp算法最简单的就是用来匹配子串，也就是从字符串s1中找到s2出现的次数与位置。同时，kmp的nxt数组还有很多高能的用处。 NXT数组：　　nxt数组是kmp算法中极其重要的部分，nxt[i]表示子串s中，上一次s[i]为后缀的位置。（看了后面的原理就很明白了） ...

字符串

2018-07-18

0 452

网络流之最小费用最大流

最小费用最大流？　　最小费用最大流就是在最大流的基础上，给每条边一个单位花费，要在保证是最大流的情况下找出最小费用。这里的单位花费就是这条边的每一单位流量的花费。解法：　　先看这里的花费，假设第i条边的花费是wi，那么假设找到了一条增广路（与最大流中的意义相同），且这条增广路的流量为x...

2018-07-17

0 491

网络流之最小费用最大流

最小费用最大流？　　最小费用最大流就是在最大流的基础上，给每条边一个单位花费，要在保证是最大流的情况下找出最小费用。这里的单位花费就是这条边的每一单位流量的花费。解法：　　先看这里的花费，假设第i条边的花费是wi，那么假设找到了一条增广路（与最大流中的意义相同），且这条增广路的流量为x...

2018-07-17

0 527

网络流之二分图匹配【转】

二分图：　二分图又称作二部图，是图论中的一种特殊模型。设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。——摘自百度百科二分图匹配： ...

2018-07-17

0 465