专业打酱油_百度空间
 
文章列表
 
2010-09-11 00:59

求关键割边……话说最近在跟andy同学的题~~

先求出来最小割,然后从src开始一次floodfill,如果u->v还有剩余容量,那么就从u转移到v;然后从sink一次floodfill,如果u->v还有剩余容量,就从v转移到u。

如果说有一条边u->v,并且u只在第一次floodfill被访问到(也就是说能从src到达u并且u不能到达sink,且v能到达sink且src不能到达v,也就是说从s到t经过u、v的这条路只被边u->v给阻塞,那么显然增大u->v的容量就可以增加流量)。

 
2010-09-10 23:57

建图:

s到每个project一条Xi的边,每个employee到t一条Yi的边。

如果project_i需要employee_j,那么project_i到employee_j一条inf的边。

把钱看作流,本来project_i能获得Xi的钱,但是其中有一部分流到了employee_j,然后被employee_j消耗掉了(实际上是从employee_j流向了t,可以看作是被employee_j吃掉了),显然按照这样构图,employee_j只能吃一次,刚好符合题意。

如果求完最大流以后,从s->v的弧没有了剩余容量,说明要么v得到的钱还不够他的employee吃的,要么刚好够他的employee吃的,

 
2010-09-10 01:47

最小割点集。

v拆点为v1、v2,之间连容量为1的弧,每条路径上的容量都是inf,要注意的是最终的pasture到sink的时候,是pasture拆出来的p1连接sink而不是p2连接sink因为可能会有超过1的流到达p1,如果用p2连接sink的话,最大流就会偏小(当然,p1、p2之间连一条inf也是可以的)

最后求从barn到sink的最大流即可。

另外,发现我写的isap跟andy同学的isap效率差别很是巨大……交上去TLE对着他的代码看了半天没看出哪儿错了,最后找来数据一跑发

 
2010-09-10 00:03

最小割唯一性判断。

正向一次最大流,然后从s开始flood_fill,如果u->v之间有一条未饱和的弧,就从u fill到v。

反向一次最大流,然后从t开始flood_fill。

如果两次floodfill遇到的点集的交集为空,并集为全集则有唯一最小割。

zoj的数据貌似有问题。。capacity可以是0,理论上来讲,如果给所有的正向弧的cap都增加1求出来的结果应该是一样的,但是zoj上如果给cap都加1就会wa掉。

 
2010-09-08 01:37
这次盖上盖子直接扔了= = 人道毁灭。。
 
2010-09-08 01:22

老鼠跑到我的可乐瓶子里面(小老鼠)。。然后我就把瓶子盖上……各种折磨最终给玩死……

希望不会做噩梦。。也希望母老鼠不要来报复……

 
2010-09-06 10:58

= =

简单对暑假集训结束后的机房进行一个总结

注:本帅是普通队员,无头衔,所以这是非官方总结——当然,如果是官方的总结也不会来找我来写,如果您期待着看到官方总结,请关注[http://hi.baidu.com/blackstar08][http://hi.baidu.com/ericxieforever]。

按人来~

首先是小灰越同学 自打

 
2010-09-05 02:47

首先如果当作一个回路来做的话,就会越想越麻烦,实际上,在返回的时候,可以把所有经过的边都反向,这样就变成了从1到N走两次,不走同一条边,使得两次长度之和最短。

如果两次长度一样,那显然是一个简单的网络流,但是现在的问题在于长度不一样,不过分析一下就会发现,如果把长度看作cost,那么刚好是一个费用流……

但是我们只需要走两次,所以添加超级源s和超级汇t,从s到1一条费用为0容量为2的边,从N到t一条费用为0容量为2的边,其余都是费用为其长度,容量为1的边,最后求一个最小费用。

做这个题

 
2010-09-04 23:17

一开始用Java写 无限RE。最后终于狠下心来用C++重写了一遍 果然过了= = 无比悲伤。。

可以看作是一个模板题,有关于算法细节请移步:http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.114.6687&rep=rep1&type=pdf

 
2010-09-02 10:09
rt 每次用手机登陆就自动被挠 TMD搞推广也不是这么搞的
 
2010-08-30 21:54

不知道效率如何。

虽然改了以后匹配有点贪心思想,但是就算匹配的不是最优的,随后的增广操作会修正这次不够优的匹配,所以最后应该能求出最优解。

 
2010-08-29 23:58

二分图的多重匹配。

修改了下HK算法,但是修改后的这个算法很可能是错误的。

HK本身是用一个一维数组来记录每个点所匹配的那个点,我修改成了用2维数组来记录每个点匹配的那些点,在bfs的时候尚容易对应过来,但是在dfs的时候原来的算法非常容易理解,修改后就有了一些贪心思想(优先直接匹配,如果不能直接匹配才会考虑增广,我之所以不知道算法的正确性就在于对增广的理解太过肤浅)。

至于range。。其实直接暴力也能过(2秒8左右(Java的时限是3倍)),

 
2010-08-29 19:04
过了cet6的大二没有英语课 哈哈~
 
2010-08-29 15:52

rt。干了些啥未知。估计他也没能进我系统,毕竟有密码

(我2点05离开的本子)

日志名称:          System
来源:            Microsoft-Windows-Power-Troubleshooter
日期:            2010/8/29 15:32:54
事件 ID:         1
任务类别:       

 
2010-08-29 00:54
rt 搬了趟宿舍 累死了 发了几本书 数据结构是英文的 还都是C 的template的代码 其实上学期我们C 没讲模板这一章 不知道其他同学会不会学的很痛苦 另外还有一本叫做现代操作系统原理 简单翻了下 大多数名词还是见过的 另外的那个计算机组成原理就比较麻烦了 还有概率论 另外 居然还有马克思...
 
     
 
 
未命名
 
 
     
 
关于我
 

这里曾经有一个原创的简介,后来抄袭的人太多了,我就把它删掉了。

A long long way to go.

   
 
友情链接
 
 
 
 
 
 
 
 
 
 
 
 
 
     
 
好友最新文章
 
     
 
最新评论
 
     
 
最近访客
 
 

arcewolos

BlackStar08

matrush

y32asm

guanpeipei888

笨小孩_shw

492943457

亚速群岛
     
 
留言板
 

回复arcewolos:- -
 

酱油教主么…我也想加入贵教捏~
 

你头象挺有意思~
 

踩过~
 

回复没玩过电脑_:特别是它头上那几根毛,有点像公鸡的~~
 
     
 
背景音乐
 
     
 
订阅我的空间
 
已有人次访问本空间
 
订阅RSS  什么是RSS?

您也想拥有这样的空间?请点此申请。
     


©2010 Baidu