苟且的狮子

题解

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

/ 注册

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

点阵

最大流，建图题意：分析：难点就在建图。我们不难这样想：将每一条边视作一个点，将每一个格子视作一个点。格子点拆成两个。然后这样建造：但是，这很明显不能满足约束条件。对于相邻的两个格点，如果他们相邻的边被选中时，两个格点的s-s1或者s2-ed都要减一，并且该边所代表的点再也不能走了！很明显我...

最大流网络流建图

2020-08-30

1 569

小Y写文章

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

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

2020-08-16

7 1244

[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 614

方格取数(2) HDU - 1569

网络流，最大权独立点集题意： ##分析：看到这一题，我的第一反应是二分图求最大独立点集。想要用HK算法干掉他。但是仔细一看并非如此，题目让球的是最大权独立点集。这就是完全不同的问题了。真正的解法推荐看论文：胡伯涛《最小割模型在信息学竞赛中的应用》，直接跳到第五部分读就行了。不得不感叹，真是巧妙...

网络流最大点权独立集最小割

2020-08-14

1 910

kebab HDU - 2883

网络流，离散化题意：分析：不妨先看看这一题：hdu3572可以先做这题会发现这两题几乎一摸一样不同之处在于：1.本题时间跨度大足足有100W,所以如果按照原先的思路我们是要对其离散化的2.本题中的肉串可以分成k块同时烤制3.本题中一种肉块有n个我们要解决这三点。先从2，3开始：一块肉可以...

网络流离散化

2020-08-14

1 504