苟且的狮子

题解

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

/ 注册

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

MAX Average Problem

论文题，再度认识了数形结合！！！所谓斜率判断时，可以划分阴影区域的，有助于判断 #include<iostream> #include<algorithm> #include<queue> #include<deque> #include<vec...

2020-11-25

2 561

Lawrence

斜率dp 第二道斜率dp问题，不会做。。。。。真是太狼狈了！！！但是也加深了对斜率dp的理解这一题，我上来就用动态规划求出了任意两仓库之间所产生的贡献度，很快啊！！！假设我们用f[i][j]来表示从仓库i到仓库j连续的这一段所产生的贡献度。f[i][j] = f[i][j-1]+(sum[j-1]...

斜率dp

2020-11-23

1 587

Print Article

斜率dp 第一道斜率dp题，终于是理解了斜率dp。点亮技能树，我会变的越来越强的！！ #include<iostream> #include<algorithm> #include<deque> using namespace std; const int max...

2020-11-23

2 508

Sabotage 来自专栏

这里学到的是一个输出最小割的方案！！！在跑完最大流后，属于最小割的边肯定cap都为零了。我们再以源点为起点进行dfs搜索，标记。然后最小割会将其阻拦住，然后我们再遍历边，看有哪些边一端被标记了另一端没有被标记。这样就好了。 #include<iostream> #include<a...

2020-11-12

2 555

Tour HDU - 3488 来自专栏

我们发现，对于一个有向图，他若是形成了一个换。那么我们把他拆点，成二分图。会发现这个二分图一定会形成一个完备匹配。那么这题就明了了。我们建立二分图，其中边的权值取负数，然后跑一遍KM就可以了。我邻接表用多了，没怎么用邻接矩阵。这里刚开始忘给矩阵付初始的值-inf了。。。。。。代码如下 #inclu...

2020-11-11

1 541

Control HDU - 4289 来自专栏

没什么难的，不难看出这是求最小割。关键是解决点权问题。我们可以拆点，拆成in和out然后连边权值为cost 之后的边正常连，只不过权值都为inf代表不可以割这里的边。然后跑个最大流就好了。 #include<iostream> #include<algorithm> usi...

2020-11-11

1 571

Food HDU - 4292 来自专栏

关键在于建图，食物放左边，饮料放右边，人员放中间。需要注意的是，人员要拆点，保证一人只能吃一份。以后都不用dinic了，都用ISAP #include<iostream> #include<algorithm> using namespace std; const int m...

2020-11-11

2 592

Island Transport 来自专栏

淦，竟然卡dinic给出IASP的模板： #include<iostream> #include<algorithm> #include<cstring> #include<queue> using namespace std; typedef lon...

2020-11-11

2 564

Work Scheduling 来自专栏

板子题，学了个带花树算法。时间复杂度O(n^3)用于求一般图的最大匹配，即有奇环的图。 struct edge{ int to,next; }E[max_m<<1]; int head[max_n]; int cnt=1; void add(int from,int to){ ...

2020-11-11

1 569

奔小康赚大钱来自专栏

竟然卡最小费用最大流。因为是稠密图的原因吗？那我们呢就用KM算法吧。这一用不要紧，我竟然发现我的KM模板竟然也被卡时间了。。。。。。赶紧更新自己的模板。 #include<iostream> #include<algorithm> #include<queue> ...

2020-11-11

2 566