苟且的狮子

题解

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

/ 注册

全部文章 / 题解（共179篇）

[HNOI2012]矿场搭建

tarjan、割点、分类讨论题意：分析：这题很容易让我们想到割点。这并不难，但是细节上的处理于分类讨论才是这道题的难点。我们想想如果一个连通块，他有一个割点。那么，我们一定要在他被割点分开的两个连通块中放置救援出口。而放置的方案数就是两边的点数相乘，割点不算！如果，他有两个以上的割点...

tarjan 割点

2020-08-29

4 550

[JSOI2010]连通数

bfs,bitset 题意： ##分析：题目没给数据范围，n<=2000考录到数据范围，这题我们可以直接bfs，或者dfs。暴力搜索。细节处理好也能过。但是，显然有些勉强。这里面考的是，bitset容器。 bitset的或运算代替了搜索。看代码： bitset<max_n> a[...

bitset bfs

2020-08-29

1 637

字符串的问题

kmp 题意：分析：我们看着一题，我们仔细想想。首先如果没有要求中间子串的话，就很简单了。我们直接输出前后缀相等的就好了。无论是 kmp 还是暴力都是线性时间。但是麻烦就在于中间要有字串。那我们想想，如何判断中间有没有子串呢？假设，next[n] = k 意味着s0,s1,s...

kmp

2020-08-28

7 619

[HAOI2006]受欢迎的牛

tarjan，dfs 题意：分析：不知道怎么回事，这道题做的时候总是有点迷迷糊糊的，犯了好多低级错误。。。。。。总之，如果接触到tarjan的话那么我们肯定能够反映过来：一定要缩点的。缩点后啊，这张图就是一张拓扑图。有向无环。每割点都有权值，就是此节点缩的点数那现在让我们从这张有向无环图中...

dfs tarjan map

2020-08-25

1 587

[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