2011年07月 存档

ZOJ 3229 Shoot the Bullet (有上下界的最大流 ,ym watashi的题)

2011年07月30日,星期六

ZOJ 3229 Shoot the Bullet 

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

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

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

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

ZOJ 1994 Budget (staus 1st,happy~)

2011年07月20日,星期三

ZOJ 1994 Budget

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

(更多…)

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

2011年07月19日,星期二

SGU 242 Student’s Morning

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

(更多…)

HDU 3599 War (dinic + dijkstra +heap )

2011年07月18日,星期一

HDU 3599 War

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

(更多…)

ZOJ 2314 Reactor Cooling

2011年07月12日,星期二

ZOJ 2314 Reactor Cooling

很裸地无源汇的可行流,我看了看论文但是不是很明白他的工作原理,虽然A了,但是心里没底。。

纯粹留下代码,方便以后用。。
(更多…)