思考一下我们接触的最小割问题 最小割的基本问题(可能会和图论的知识相结合,比如bzoj1266,bzoj1797) 最大权闭合图(bzoj1497) 最大点权覆盖集,最大点权独立集(bzoj1324) 最近接触到了一类关于最小割新的问题,我也不知道叫什么好 反正它有这么几个特点 每个点都有两种选择的可能性,设为属于S和属于T,属于S有收益a[i],属于T有收益b[i] 两点之间可能因为同在一个或不在同一个集合内产生额外的收益 使收益最大化(废话) 大概就是这个意思,如果看不懂也没关系,我们先从最

题面 BZOJ传送门 Luogu传送门 分析 考虑如何最小割建图,因为这仍然是二元关系,我们可以通过解方程来确定怎么建图,具体参考论文 <<浅析一类最小割问题 湖南师大附中 彭天翼>> 那么我们来看看怎么解方程 设存在一对二元关系<x,y><x,y><x,y>,那么假设分在SSS一边表示不雇佣,TTT一边表示雇佣.先把总收益全部加起来,那么只要考虑会每种情况会在此基础上减去多少. 如果两个都雇佣 : a+b=A[x]+A[y]a+b=A[x]+A

二分图基础: 最大匹配:匈牙利算法 最小点覆盖=最大匹配 最小边覆盖=总节点数-最大匹配 最大独立集=点数-最大匹配 网络流: 技巧: 1.拆点为边,即一个点有限制,可将其转化为边 BZOJ1066,BZOJ1305 2.考虑左右两部,即比如横竖.男女.比赛和人等. BZOJ1532 带下界网络流问题 ----------------------转自zyf-zyf ss和tt为附加源或者说超级源 1.无源汇上下界可行流 对于(u,v)有向边,上界为a,下界为b 构图方法为: (1) ss 到 v

题目 输入格式 第一行是三个正整数P,Q,R,表示切糕的长P. 宽Q.高R.第二行有一个非负整数D,表示光滑性要求.接下来是R个P行Q列的矩阵,第z个 矩阵的第x行第y列是v(x,y,z) (1≤x≤P, 1≤y≤Q, 1≤z≤R). 100%的数据满足P,Q,R≤40,0≤D≤R,且给出的所有的不和谐值不超过1000. 输出格式 仅包含一个整数,表示在合法基础上最小的总不和谐值. 输入样例 2 2 2 1 6 1 6 1 2 6 2 6 输出样例 6 提示 最佳切面的f为f(1,1)=f(2,

1001: [BeiJing2006]狼抓兔子 Time Limit: 15 Sec  Memory Limit: 162 MBSubmit: 19528  Solved: 4818[Submit][Status][Discuss] Description 现在小朋友们最喜欢的"喜羊羊与灰太狼",话说灰太狼抓羊不到,但抓兔子还是比较在行的, 而且现在的兔子还比较笨,它们只有两个窝,现在你做为狼王,面对下面这样一个网格的地形: 左上角点为(1,1),右下角点为(N,M)(上图中N=4,M

模型要点: 1.一般适用于二取一问题或者01规划. 2.利用最小割=最大流,转化为最大流求之. 建议阅读胡伯涛的论文 <<最小割模型在信息学竞赛的应用>>,有精彩有序的证明和各种模型,不过我大概花了2个星期才把它弄懂...最小密度路径的改进算法那一块的推导前面部分有些问题,但后面是对的,结论也是对的,蛋疼了好久.. 相关题目: 1.太空飞行计划(网络流24题) 题目大意: 有一些实验和仪器,做每个实验有相应的报酬,但是需要买好相应的仪器(多个实验可以共用),仪器需要相应的钱.求最大

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1001 现在小朋友们最喜欢的"喜羊羊与灰太狼",话说灰太狼抓羊不到,但抓兔子还是比较在行的,而且现在的兔子还比较笨,它们只有两个窝,现在你做为狼王,面对下面这样一个网格的地形: 左上角点为(1,1),右下角点为(N,M)(上图中N=4,M=5).有以下三种类型的道路 1:(x,y)<==>(x+1,y) 2:(x,y)<==>(x,y+1) 3:(x,y)

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1001 很有意思的题目,本来想直接上网络流,但是发现点太多,边太多2333. 直接网络流无法做. 然后学到一个新的东西——平面对偶图求最大流. 性质很好用. 组要看这篇文章:周东的<浅析最大最小定理在信息学竞赛中的应用>很强大 我们知道求最大流有两种一种是求出增光路,另一种是求出最小割. 这里转化成最短路,转化的时候都点烦. 不过真心不错

1.点云分割的精度 在之前的两个章节里介绍了基于采样一致的点云分割和基于临近搜索的点云分割算法.基于采样一致的点云分割算法显然是意识流的,它只能割出大概的点云(可能是杯子的一部分,但杯把儿肯定没分割出来).基于欧式算法的点云分割面对有牵连的点云就无力了(比如风筝和人,在不用三维形态学去掉中间的线之前,是无法分割风筝和人的).基于法线等信息的区域生长算法则对平面更有效,没法靠它来分割桌上的碗和杯子.也就是说,上述算法更关注能不能分割,除此之外,我们还需要一个方法来解决分割的“好不好”这个问题.也就

3144: [Hnoi2013]切糕 Time Limit: 10 Sec  Memory Limit: 128 MBSubmit: 681  Solved: 375[Submit][Status] Description Input 第一行是三个正整数P,Q,R,表示切糕的长P. 宽Q.高R.第二行有一个非负整数D,表示光滑性要求.接下来是R个P行Q列的矩阵,第z个 矩阵的第x行第y列是v(x,y,z) (1≤x≤P, 1≤y≤Q, 1≤z≤R). 100%的数据满足P,Q,R≤40,0≤D≤

Problem Description 欢迎来到珠海! 由于土地资源越来越紧张,使得许多海滨城市都只能依靠填海来扩展市区以求发展.作为Z市的决策人,在仔细观察了Z市地图之后,你准备通过填充某些海域来扩展Z市的海岸线到最长,来吸引更多的游客前来旅游度假.为了简化问题,假设地图为一个N*M的格子,其中一些是陆地,一些是可以填充的浅海域,一些是不可填充的深海域.这里定义海岸线的长度为一个联通块陆地(可能包含浅海域填充变为的陆地)的边缘长度,两个格子至少有一个公共边,则视为联通. 值得注意的是,这里Z市

1001: [BeiJing2006]狼抓兔子 Time Limit: 15 Sec  Memory Limit: 162 MBSubmit: 23822  Solved: 6012[Submit][Status][Discuss] Description 现在小朋友们最喜欢的"喜羊羊与灰太狼",话说灰太狼抓羊不到,但抓兔子还是比较在行的, 而且现在的兔子还比较笨,它们只有两个窝,现在你做为狼王,面对下面这样一个网格的地形: 左上角点为(1,1),右下角点为(N,M)(上图中N=4,M

http://www.lydsy.com/JudgeOnline/problem.php?id=1001 题意: 思路:这道题目是最小割题目,但是吧你直接套用Dinic是会超时的. 这里有种很奇妙的做法啊,具体可以参见论文:<浅析最大最小定理在信息学竞赛中的应用>--周冬 S-T平面图:首先是一平面图(满足欧拉公式与存在对偶图),且源点S,汇点T在边界上.将S-T连线,将最外面的一个大面(无限大)一分为二了,一个为S,一个为T.然后将每条边两边的面相连,权值就是该边权值.最后跑最短路,它经过的

Description 传送门 Solution 此处我们按最小割的思路考虑. 暴力:S->i表示该点选黑色的权值b[i]:i->T表示该点选白色的权值w[i].考虑如果某个点i受点j为白点的影响,则将点i连向点j,边权为p[i].但这么做假如有多个点j,p[i]就会被算多次.可以将i点拆为i和i'.则将i'连向j,边权为inf(即该边不能割),将i连向i',边权为p[i]. 不过这么搞肯定要爆.考虑一下怎么优化. 我们发现最耗空间的是i'->j的边.(如果l[i],r[i]给的范围大的

浅析最大最小定理在信息学竞赛中的应用---周东 ↑方法介绍 对于一个联通的平面图G(满足欧拉公式) 在s和t间新连一条边e; 然后建立一个原图的对偶图G*,G*中每一个点对应原图中每一个面,每一条边对应分割面的每一条边; 那么对偶图G*中,以原图s和t间边e新划分出的面作为起点(s*),最外的面作为终点(t*); 那么从s*到t*的每一条路都是原图G的一个割; 下图来自上方标出百度文库网址的ppt; 然后用堆(优先队列)优化的迪杰斯特拉,复杂度 O((m+n)logn) n为点数,m为边数...

传送门 考虑一下,答案就是全局和减去舍弃和 不难发现,如果我们按行数+列数的奇偶性分为两类,那么每一类中的数必然互不相邻 那么我们把原图的点分为黑点和白点两类,原地向白点连边,黑点向汇点连边,容量为点权,然后白点向相邻的黑点连边 考虑一下,不能有相邻的,就是在残留网络中不能有$s->u->v->t$这一条路径,那么肯定要在某一个地方割掉.然后要求和最大,所以求得是最小割 然后最小割等于最大流,求一下最大流即可 //minamoto #include<iostream> #in

1.点云分割的精度 在之前的两个章节里介绍了基于采样一致的点云分割和基于临近搜索的点云分割算法.基于采样一致的点云分割算法显然是意识流的,它只能割出大概的点云(可能是杯子的一部分,但杯把儿肯定没分割出来).基于欧式算法的点云分割面对有牵连的点云就无力了(比如风筝和人,在不用三维形态学去掉中间的线之前,是无法分割风筝和人的).基于法线等信息的区域生长算法则对平面更有效,没法靠它来分割桌上的碗和杯子.也就是说,上述算法更关注能不能分割,除此之外,我们还需要一个方法来解决分割的“好不好”这个问题.也就

继续补坑.. 第三天主要是网络流 首先我们先了解一下网络流的最基本的算法:dinic 这个算法的主要做法就是这样的: 在建好的网络流的图上从源点开始向汇点跑一遍BFS,然后如果一条边的流量不为0,那么就往下标号, 每一个点的level都是上一个点的level+1 然后在跑一遍DFS,如果发现边的两个点的level差值为1(终点比起点的level大),那么就走这条边. 那么我们首先要了解一下如何建边 网络流的最基本概念就是:可以反悔 就是说假如说我们有更好的方案,那么我们可以把原来流掉的流量再流回

题意:有一张平面图,求它的最小割.N,M.表示网格的大小,N,M均小于等于1000. 左上角点为(1,1),右下角点为(N,M).有以下三种类型的道路  1:(x,y)<==>(x+1,y)  2:(x,y)<==>(x,y+1)  3:(x,y)<==>(x+1,y+1)    思路:第一眼看就是一个最小割=最大流,但点数1000000,边数6000000过大 所以要平面图最小割转最短路 详情见周驿东<浅析最大最小定理在信息学竞赛中的应用> n=1和m=1

第一次做最小割,不是很理解. https://www.luogu.org/problemnew/show/P1361 要把东西分进两类里,好像可以应用最小割的模板,其中一类A作为源点,另一类B作为汇点,价值就是边的容量. 然后最小割一定会割断每个中间结点的两边的其中一边,这样最大价值就顺带求出来了. 在这道题里面额外还有某些点成组出现的额外价值.题解的办法是分别虚拟两个结点代表两个集合,源点到集合a的容量是其价值,然后从a连到他的附属结点各边容量为无穷.无穷的边不能被最小割割断.所以要么是把a的