苟且的狮子

分类

2020多校(6) CF(27) 作业(3) 区域赛真题题解(提升思维！！！)(8) 寒假模拟赛(1) 未归档(1) 苏州大学排位赛(7) 随笔(1) 题解(180)

/ 注册

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

kuangbin题单刷题详解(最短路篇)

9篇文章 696人学习

kuangbin题单刷题详解(网络流)

10篇文章 648人学习

kuangbin题单刷题详解(匹配问题)

14篇文章 724人学习

kuangbin刷题题单详解(后缀数组)

8篇文章 588人学习

kuangbin刷题题单详解(博弈论)

8篇文章 737人学习

kuangbin刷题题单详解(连通图)

9篇文章 814人学习

Kuangbin刷题详解(AC自动机)

4篇文章 613人学习

Kuangbin题单详解(kmpManacher)

20篇文章 950人学习

Kuangbin题单详解(区间dp)

6篇文章 791人学习

全部文章（共229篇）

[AHOI2009]MINCUT 最小割

结论题，最小割，tarjan 题意：分析：题目看了，就是让我们对图中的每一条边都做判断：是否可以是最小割边？是否一定是最小割边？暴力做法：n*m对于每一条边我们都单独判断！那么现在来看tarjan做法：首先让我们想想，传统如何判断一条边能不能在最小割集中。先跑最大流，得到其残余网络(此残余...

最小割唯一性判断最小割

2020-08-19

1 630

团结就是力量

字符串同构，tarjan，hash 题意：分析：不难想到用tarjan算法，将互相愿意组队的人员划分出来。但是，稍微有困难把你的便是：如何计算这只队伍的团结系数呢？这里牵扯到了一个知识点：字符串同构！！对于字符串a,和字符串b我们知道a经过一定的循环就会变成b。我们称a与b同构。那么倘若我...

同构字符串 tarjan hash

2020-08-19

4 710

[CQOI2012]交换棋子

建图拆点，最小费用最大流题意：分析：首先我们认识到，对于我所在的棋盘，如果我把所有的黑子都摆放在指定的位置上了的话，那么白子也一定被摆在了指定的位置。所以，这里我们不妨只看黑子，考虑让其摆放在规定的黑子位置上所消耗的步数最小。不难想到，这是个匹配问题。我们要对所有的黑子对其归属位置进行匹...

最小费用最大流思维建图

2020-08-18

4 811

Coding Contest

最小费用最大流，对数乘法换加法，浮点数比较题意：这道题看上去很裸，似乎就是一道最小费用流的题目。需要注意的有三点：1.这里面最小费用的计算是乘法，所以我们要对其取对数将其变为加法。2.因为e(u,v)的cost为浮点数，所以再spfa算法中我们便不能再直接比较了。需要加上个eps否则会一直超...

最小费用最大流对数乘法换加法浮点数比较

2020-08-17

1 600

小Y写文章

网络流，二分、二分图最大匹配题意：分析：这一题出的好啊！！！！正是我能力边缘的题目。有助于提升实力！！！我们需要插入m段广告，有n+1个空位我们可以插入。当插入时，我们整体得不流畅度可能会改变。当我们看到max() 时，我们就应该尝试用二分的思想取考虑一下，a1,a2,a3,a4当我们...

二分最大流网络流二分图最大匹配建图

2020-08-16

7 1232

[CQOI2014]危桥

最大流，反复跑流题意：分析：这题我不会，是看人题解后做的。汗这题有两个收获：1.网络流建无向图。 void add(int from, int to, int cap) { E[cnt].to = to; E[cnt].cap = cap; E[cnt].rev ...

反复跑图网络流

2020-08-16

0 609

Birthday

最大流，二分题意：分析：这一题，我刚拿到手是蒙B的。我的第一反应也是最小费用最大流，但是想了一会也是不知道该如何表示X^2这个万恶的东西。迫不得已，展开别的思路：我们这样建图：源点S与1~n相连，取cap = 1 无cost1~n与n+1 ~ n+m 按照数据相连 cap = 1,无c...

二分最大流

2020-08-16

1 641

[SDOI2010]星际竞速

建图，网络流，最小费用最大流题意：分析：雨神说过，图论题难就难在建图上。这题我觉得建图还是蛮难的。我们捕捉一下重要信息：从一个额外的点出发，恰好经过每一个点一次，可以进行跳跃，永远是小点连大点。我们不难明白，所谓额外的点其实就是时空跳跃的中介点，也同时是起点。同时，我们也很本能的想将所...

最小费用最大流建图

2020-08-15

2 968

勤奋的杨老师（二）

最大点权闭合子图题意： ##题解：这时一道非常模板的最大点权闭合子图问题。但是，我们不知道最大点权闭合子图是什么。。。。。。现在，有我来告诉你：有一堆有权值的点，权值可以为正为负为零。这些点有一些如图的相对顺序：即，这个图中会有一些树！图可能原本是这样的：图具体长什么样无所谓，你只要知道这些图...

最大点权闭合子图

2020-08-15

2 583

Collect Jewel

最小费用最大流题意：分析：这是我第一次做最小费用最大流的题目。感觉还行，写个题解留作纪念。意识到这是个关于最小费用最大流问题并不难。但是，关键在于如何建图。拆点是一定的。我刚开始想，对每一个节点，拆成两个。原节点到拆点一条c=1 d=-vi 的路拆点到原节点一条c=inf,d=0的路。...

最小费用最大流

2020-08-15

1 576