UVA 10246 Asterix and Obelix (最短路变形)

UVA 10246 Asterix and Obelix

乍看是带点权的最短路,实际上最短路再加上最大点权最小的时候才是最短,即min{ path(S,T) + min{w[i]|i on path from S to T}}.我表示没有思路,看的题解做的。。比如说我们要求出S,T的“最短路”,我们可以枚举最大中间节点,因为这条路必经经过一个最大中间节点,比如说我们找到点U的时候,就假设U是S到T路径上点权最大的点,可以把图上点权大于U的点去掉然后d[ S, U ] + d[ U, T ] + w[U]便是假设u点权最大时候的“最短路”,每给出一个询问,查询即可。

(更多…)

继续阅读 →

POJ 2125 Destroying The Graph (最大点权覆盖集)

POJ 2125  Destroying The Graph

破坏一个棵树的,就是把他的所有边都删掉,现在有两种方式就是删掉i点的所有入边,还有就是删掉i点的所有出边,所需要的费用为Wi+,Wi-,每一条边<u,v>要被销掉,要么删除u的所有出边,要么删除v的所有入边,每条边都至少与一种操作相关联,我们可以联想到二分图的最小点集覆盖,求最小的点集,让所有的边都与之关联。对于这个题来说就是典型的模型了。二分图的最小点权覆盖,AMBER的论文第30页有讲,不再赘述,注意不要把边权选错了,入度的权在右边。。。我因为这个搞了一个下午。

还有,我的最大流模板已经十分完善了,就在blog上放我的模板,以后会填上费用流,强连通等的并且不断改进:

 

(更多…)

继续阅读 →

POJ 2987 Firing (构图 最大点权闭合集)

POJ 2987 Firing

题目就不在赘述,很裸的最大点权闭合集,在《最小割模型在信息学竞赛中的应用》有证明,但是呢,我看的不是很懂,今天早上看了一早上,下午又看了一会,还不是很明白,真坑跌,我怎么就理解不了最小割呢?哎,路漫漫,网络流的各种模型我什么时候才能搞懂啊 = =

虽然我不懂,,,但是AC还是没有问题的。。。
(更多…)

继续阅读 →

POJ 1149 PIGS (建图搞死人= =)

POJ 1149 PIGS

以前刚开始看网络流的时候,下载过一个文档,《网络流建模汇总 by Edelweiss》,里面第一个模型就是这个题,当时看了好长时间,没看懂= =b,这两天重新看过之后,思路清晰了许多。网络流难的不是dinic,sap呀什么的,是建图,搞死人呢。。。

经过一番搜题解之后,我发现最详细的解释出自这里,凑活着看吧,上面的文档中也有(不过我打印出来是黑白的,图示不清)。
(更多…)

继续阅读 →

ZOJ 3229 Shoot the Bullet (有上下界的最大流)

ZOJ 3229 Shoot the Bullet 

前几天看了有上下界的各种流,使劲看啊使劲看,终于有点眉目,然后就刷这个题去了。。然后就被虐了= =

之前看书说是求最大流的时候需要二分下界看是否有可行流,但是,我想来想去,这尼玛坑爹啊,怎么都会超时的,但是试了各种二分,dinic,sap都用了,就是超时,感觉一定有什么不对劲,放那里,过两天再看。。

今天小媛赐予我《新编实用算法与程序设计》,俗称蓝书,看了看二分图部分后,就顺便看了看网络流的部分,里面有讲这个,我仔细看了看,终于理解了求可行流时候为什么要那样构图,而且发现其实不用二分下界,只需要删掉T->S的弧,然后求个S,T的最大流就行了。。因为下界(必满,已经在求可行流时候满足了)没有包含在残量网络里,所以直接扩流就行了  = =。。。

对于本题,因为有些奇怪的单词,可能读题比较困难,n天给m个mm拍照,每个mm有拍照数量下限,每天有拍照数量的上界,每天拍照某个mm也有数量限制,求这n天能拍到的最多的mm数,和每天拍的数量。建图很弱啦。。。。代码木有注释,。。。凑活着看吧。。。=  =
(更多…)

继续阅读 →

ZOJ 1994 Budget (staus 1st,happy~)

ZOJ 1994 Budget

这个题同时也还是POJ上的2396,经典的有上下界的可行流,我的模板已经经过好几个网络流题目的考验了,这道题排到zoj的第一版,实在是激动啊。刚开始我还想着是对于矩阵中的每一个格子都建立一个点,但是看过别人的建图,发现这个可以省略成行到列的弧。把每个行看成一个点,每个列也看成一个点,行到列的弧就可以看成是对应格子的流量。源点S到行点的弧容量上下界都是行的和(题目中给出),列点到汇T的容量同样是列的和,T到S再建立[0,inf]的弧,那么就可以用无源汇的可行流解决了。。

(更多…)

继续阅读 →

SGU 242 Student’s Morning (有上下界的可行流)

SGU 242 Student’s Morning

学生要去学校游玩,每个学生有几个喜欢的学校,要求每个学校至少有两个人,我们可以这样建图,从学校到学生建立[0,1]的弧,从学生到汇点T,建立[0,1]的弧,对于每个学校从源点建立下界为2的弧,从T到S建立[0,2*K]的路,这样就可以用模板了。今天晚上来到实验室,完全手写的代码,竟然一次AC了,十分高兴,而且代码也些的很工整,用作网络流的模板啦~

(更多…)

继续阅读 →

HDU 3599 War (dinic + dijkstra +heap )

HDU 3599 War

类似于zoj2760 how many shortest paths,需要求出有多少个互不相交的最短路条数,需要求出最短路,然后让满足d[to]  == d[from] + w[from][to] 的两个点间连接一条弧,容量为1,然后再S,T之间求最大流即可,本题难度 不大,就是出数据的人该遭鄙视,边的顶点竟然有为0的,害得我搞了好长时间,求最短路的时候可以用spfa和dij+heap,速度差不多,哎,好久么有写最短路了,我这个代码写了好几遍,我感觉已经写的非常规范了,可以当做模板用。。。

(更多…)

继续阅读 →