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,速度差不多,哎,好久么有写最短路了,我这个代码写了好几遍,我感觉已经写的非常规范了,可以当做模板用。。。

(更多…)

继续阅读 →

ZOJ 3195 Design the city (lca + st )

ZOJ 3195 Design the city

给出n个区域,有n-1条路去连接这些区域,显然他是一个带权无根树。首先把它以0为根看成有根树,对于给出的三个点,每两个点之间的距离是固定的,因为他们之间只有一条路,但是对于这么多查询(at most 70000 ),直接找距离代价太大,找出每两个点的LCA,这样就可以两个点之间的距离了,(需要知道从0点开始到这两个点的距离)。 我们把这三对点的距离加起来再除以2,就能得到连接着三个点的最短路径。

(更多…)

继续阅读 →

ZOJ 2067 White Rectangles (greedy)

ZOJ 2067 White Rectangles

好久没有更新博客了,突然间想做几个贪心题目,于是就照着大黄的贪心题目分类开始刷。

题目描述的很清楚,给出n*n的地图,需要找出全部由白色点组成的矩形的个数。刚开始想到的是枚举,不过这个复杂度也太高了。需要做一个预处理,需要统计处从某一点开始向右最长的连续白点个数,保存在rightt中。然后进行枚举每个点,统计以他为左上角的矩形的个数,其间还要枚举高度。。时间复杂度O(N^3)

(更多…)

继续阅读 →

第三届郑州轻工业学院校赛流水帐~

A.水题..注意从两个门开始搜

B.矩阵快速幂求第n个fibnacci数,但是当时比赛的时候不知道这个算法阿…依稀记得算法导论的视频上有个矩阵运算,然后我就坐在那里一直YY……最后……居然yy出来了,我了个汗阿…..但是不会求时间复杂度,但是我好像感觉比那个幂预算稍微慢点…..附上代码,路过的大牛,指导下把..
(更多…)

继续阅读 →

有点小高兴

在uva上刷题前看了看status版,看到了suneast牛,我想,uva上牛人众多,像我这样的小菜菜应该没有机会挤到第一版了吧。。。。。经过几次tle之后ac了,到第一版一看,我竟然排到了suneast前面,十分激动啊~ 💡

继续阅读 →

ZJU集训选拔分数判定器 (dt了..= =)

今天edward_mj说到浙大的集训选拔分数统计有点难搞,我就萌生写个py脚本来统计分数的想法,正好最近py手生,说搞就搞~

统计标准在这里:

狗狗40题(这里的1001-1040) 2.5分/题
Andrew Stankevich’s Contest 1.5分/题
其余ZOJ中所有题号的质数的题 1分/题
其余题目 0.3分/题

这是关于zoj题目的统计,我主要就是搞这个,主要框架就是一个if else 语句,难点就是提取那几个题的题号,一步一步来:

一、提取狗狗40题题号:

shi哥的blog有现成的题号,但是还需要分离,复制网页html代码,然后通过文件找出题号,我用的是很笨的方法,找到那一行,再找到那一个数字= =

f = open("40.txt","r")
fp = open("out.txt","w")
for i in range(1,241):
    a = f.readline();
    if i%6 is not 4:
        continue
    fp.write(a[4:8]+",")

(更多…)

继续阅读 →