ComplexPug

分类

做题记录(1) 未归档(274)

/ 注册

全部文章（共17篇）

bzoj1001狼抓兔子对偶图优化

bzoj1001狼抓兔子对偶图优化链接 https://www.lydsy.com/JudgeOnline/problem.php?id=1001 思路菜鸡总是要填坑的！很明显让你求网格图的最小割不过1000*1000明显不能跑dinic(虽然可以水过) 我们可以用对偶图来优化辣。...

网络流对偶图图论最短路

2019-03-14

0 553

bzoj1458: 士兵占领网络流

链接 https://www.lydsy.com/JudgeOnline/problem.php?id=1458 也可以去luogu 思路想成倒着删去点，使得依旧满足覆盖！！左边横，右边列，之间用点链接起来，流量1 S到i为之间总公共最多去掉m-h[i]-L[i]个，i到T同理。代码...

网络流

2019-03-09

0 501

bzoj1497 [NOI2006]最大获利最大权闭合子图

链接 https://www.lydsy.com/JudgeOnline/problem.php?id=1497 思路最大权闭合子图的裸题一开始知道是这个最大权闭合子图(虽然我不知道名字)，但是我不理解所以还是去复习了一遍。 Orz 错误写读入优化的时候迷迷糊糊的多打了等号代码...

网络流最大权闭合子图

2019-03-09

0 478

bzoj1565: [NOI2009]植物大战僵尸最大权闭合子图，tarjan

bzoj1565: [NOI2009]植物大战僵尸链接 https://www.lydsy.com/JudgeOnline/problem.php?id=1565 思路很容易的想到最大权闭合子图但这个图是有环的有环的地方当然是都过不去的地方显然他所保护的地方也是过不去的他保护的地...

最大权闭合子图 tarjan 网络流

2019-03-10

0 530

luogu2046[NOI2010]海拔对偶图优化

luogu2046[NOI2010]海拔对偶图优化链接 https://www.luogu.org/problemnew/show/P2046 思路海拔一定是0或者1，而且会有一条01交错的分界线。转化为最小割，用对偶图优化求得。最小割论文写的特清楚。代码 #include &...

网络流最小割对偶图

2019-03-14

0 574

loj6068. 「2017 山东一轮集训 Day4」棋盘二分图，网络流

loj6068. 「2017 山东一轮集训 Day4」棋盘链接 https://loj.ac/problem/6068 思路上来没头绪，后来套算法，套了个网络流经典二分图左边横，右边列先重新算一下行和列，就是他们x相通的的算一个然后就去掉了障碍的作用然后每一行贡献是递增的(0,...

网络流二分图

2019-03-29

0 576

bzoj4501 旅行

bzoj4501: 旅行链接 bzoj 思路我居然一上来就的去重边，***真可爱。如果没有修改的话就是一个拓扑dp。 \(f[u]=\sum\frac{f[v]+1}{numson}\) 修改的话a[i]表示这个边要不要。 \(f[u]=\frac{\sum (f[v]+1)*a[i]...

网络流分数规划最大权闭合子图

2019-06-10

0 537