[BZOJ1391]解题报告|网络流的又一类建图&Dinic的若干优化

1391: [Ceoi2008]order

有N个工作，M种机器，每种机器你可以租或者买过来. 每个工作包括若干道工序，每道工序需要某种机器来完成,你可以通过购买或租用机器来完成。现在给出这些参数，求最大利润

　　关于建图和思路

　　刚开始看这道题的时候十分纠结，任务的做与不做，应当是典型的最小割取舍模型

　　然而买机器和租机器，又是常见的最小费用最大流模型的标志

　　进一步思考，对于每一对如下关系（任务）-（机器）

　　一共有三种处理方法：

　　1）任务不做

　　2）租用机器

　　3）购买机器

　　好像看出了点眉目，对于第一种情况割掉做任务的收益边其他保留

　　对于第二种情况割掉租用机器的费用边第三种情况割掉购买机器的费用边

　　于是我们可以将s连接每一个任务，每台机器连接t，每个任务和每个机器之间连接租用的费用

　　这样图就建好了，再体会一下觉得真的很有趣

　　如果说前几道变形题运用的是s,t的多种含义的话，我认为这道题就是将边的含义多重化

　　既可以表示割了就得不到保留就仍可以拥有的收益，又可以表示割了就需要付出不割就什么都不干的费用

　　具体实现过程——Dinic的时空优化

　　然而这道题的数据范围有1200，用普通的Dinic是过不了的

　　于是开始了漫长艰辛的优化之路（捂脸熊

　　首先点开hzwer学长的blog，发现了一个叫做当前弧优化的东西

　　大概就是每次dfs的时候对于每一个点假设上次做到第x条边，这条边是做完之后的容量还大于0

　　第二次做的时候前x-1条是没必要做的

　　因为要不就是都不符合条件的边，就算符合也将所有的容量都已经挖掉了

　　所以直接从“当前弧”开始做就可以了（好形象啊

　　第二个优化是dfs做完返回值前我们可以加一道特判：

　　如果当前点扫下来之后积累的所有流量都为0，说明这一点出去所有的边都不具有可用的容量

　　这个时候下一次就没必要再到这个点来了

　　于是将dis[p]赋成一个乱七八糟的东西（但是切记不要赋-1啊，万一到s点去了怎么办啊TAT

　　虽然说跳出了之后就不可能再进来了但是这种东西写这里很虚啊...

　　第三个优化是空间优化，这道题瞄了一眼空间限制64MB吓傻，我粗略估计了一下边的数组，大概有近50MB

　　也就是说我再开一个可能就开不下了...

　　这次比较幸运可万一考试的时候限制正好卡在那里怎么办？

　　发现了一个rec数组完全不用开...rec数组在整个过程中的应用只有一条语句

　　然而实际上如果我们的边下标从0开始计，rec数组有一个很奇妙的性质就是rec[j] = j ^ 1（异或）

　　平时的题我不愿意去用因为一旦下标从0开始计意味着写得很熟练的

　　while j<>0 do 就要改写法了，并且link,next这些数组初值都要重新赋了

　　但是起码知道这样一个优化方法也是好的说不定在考试的时候适用呢

　　毕竟rec数组只是为了书写方便，而异或的方法不仅用起来爽而且时间空间上都有节省

　　加油吧

　　17/.Apr.

巴特西