回归梦想

分类

dfs(2) leetcode(3) PTA(5) python(1) 一起开心(1) 后缀数组(2) 图论(4) 多校(4) 天梯赛(8) 字符串(8) 数据结构(1) 未归档(539) 模板(4) 每日一题(56) 点分治(2) 牛客题霸(117) 知识(4) 算法(76) 经验分享(2) 网络流24(11) 莫比乌斯反演(2) 队列(2) 题解(271)

/ 注册

TA的专栏 41篇文章 0人订阅

16篇文章 978人学习

牛客每日一题

6篇文章 776人学习

0篇文章 0人学习

0篇文章 0人学习

0篇文章 0人学习

3篇文章 685人学习

ACwing寒假每日一题（提高组）

3篇文章 780人学习

13篇文章 912人学习

全部文章（共1124篇）

B-Suffix Array

B-Suffix Array 题意：一个字符串只含有a和b，先给出b数组的构造方式：对于每个位置i来说：如果存在一个位置j，使得j<i,且s[j] == s[i],则b[i]=i-j 否则b[i]=0现在对字符串每个后缀都构造B数组，并按照字典序排序题解：参考博客题目标题就已经透露...

后缀数组 ***** 思维

2021-01-20

2 641

H.Minimum-cost Flow

H.Minimum-cost Flow 题目：其实就是给出每条边的单位费用，q次查询，每次查询改变所有边的容量（所有边容量一样），问最后流出1流量的最小花费是多少？题解：暴力做法肯定是每次询问都改一次容量，但是肯定会超时，想想其他方法对于题目的每次询问，每条增广路的容量为u/v，所需最大流是1...

最小费用最大流 **** 思维

2021-01-20

0 574

1 or 2

题目描述Bobo has a graph with n vertices and m edges where the i-th edge is between the vertices ai and bi. Find out whether is possible for him to choose...

ing 带花树 ***

2021-01-20

0 604

带花树算法

对于一般的二分图匹配我们肯定会想到匈牙利算法，但是如果图中出现奇环怎么办？此时匈牙利算法就不可以了，就需要另一个算法：带花树算法主要就是为了解决奇环的问题我们匹配时会发现，如果存在奇环，传统的匈牙利算法在一个奇环里至少有一个点不能匹配，那么干脆就把这个奇环缩成一个点（也叫开花，这就是算法名字的由来）...

带花树算法 ***

2021-01-20

0 1467

[CTSC1999]家园 / 星际转移问题

[CTSC1999]家园 / 星际转移问题题意： • 由于人类对自然资源的消耗，人们意识到大约在2300 年之后，地球就不能再居住了。于是在月球上建立了新的绿地，以便在需要时移民。令人意想不到的是，2177 年冬由于未知的原因，地球环境发生了连锁崩溃，人类必须在最短的时间内迁往月球。现有n个太空...

网络流分层图

2021-01-19

0 609

餐巾计划问题[网络流24题]

题意： • 一个餐厅在相继的N 天里，每天需用的餐巾数不尽相同。假设第i天需要ri块餐巾(i=1，2，…，N)。餐厅可以购买新的餐巾，每块餐巾的费用为p分；或者把旧餐巾送到快洗部，洗一块需m天，其费用为f 分；或者送到慢洗部，洗一块需n 天(n>m)，其费用为s<f 分。每天结束时，餐厅...

ing **** 网络流思维

2021-01-19

0 606

Codeforces1437 E. Make It Increasing（LIS）

Codeforces1437 E. Make It Increasing（LIS）题意：你有一个长度为n的数列a和一个含有k个不同整数的集合b，b中的数都在[1,n]内。现在你可以进行一些操作，每次操作中你可以选择两个数i和x，并将x赋值给ai。其中1<=i<=n，但i不能...

LIS 思维

2021-01-19

0 749

P4009 汽车加***驶问题

题目描述：题解：看了很多题解，无论什么解法都绕不开分层图在本题中加满油的车每次可以移动K步，那么我们就可以建立一个K+1层的分层图，表示汽车油量k的状态（油量0...k），然后根据题目要求建图首先我们规定(k从1开始)第k层第i行第j列点编号为(k-1) * n * n + (i-1) * n...

网络流分层图

2021-01-18

0 669

[USACO09FEB]Revamping Trails G

题意：约翰一共有 N 个牧场.由 MM 条布满尘埃的小径连接。小径可以双向通行。每天早上约翰从牧场 1 出发到牧场 N 去给奶牛检查身体。通过每条小径都需要消耗一定的时间。约翰打算升级其中 K 条小径，使之成为高速公路。在高速公路上的通行几乎是瞬间完成的，所以高速公路的通行时间为 0。请帮助约...

** 分层图

2021-01-18

0 767

[ZJOI2010]网络扩容[网络流24题]

[ZJOI2010]网络扩容[网络流24题] 题意：给定一张有向图，每条边都有一个容量 c 和一个扩容费用 w。这里扩容费用是指将容量扩大 1 所需的费用。求：在不扩容的情况下，1 到 n 的最大流；将 1 到 n 的最大流增加 k 所需的最小扩容费用题解：第一问好说就是跑最大流，关键...

网络流

2021-01-18

0 654