当前位置:首页 > 图论 > 网络流 > 正文
[上下界最大流]ZOJ3229ShoottheBullet
3593+

题目大意:一个屌丝用n天时间给m个女神拍照,每一天屌丝只能给给定的Cj个女神拍照,该天给女神i拍照的数量要在[Li,Ri]范围内,每天拍照数不能超过Di张,每个女神n天的拍照总和不能少于Gi,如果有解求屌丝最多能拍多少张照,并求每天给对应的Cj个女神分别拍多少张照;否则输出-1。

Gensokyo is a world which exists quietly beside ours, separated by a mystical border. It is a utopia where humans and other beings such as fairies, youkai(phantoms), and gods live peacefully together. Shameimaru Aya is a crow tengu with the ability to manipulate wind who has been in Gensokyo for over 1000 years. She runs the Bunbunmaru News – a newspaper chock-full of rumors, and owns the Bunkachou – her record of interesting observations for Bunbunmaru News articles and pictures of beautiful danmaku(barrange) or cute girls living in Gensokyo. She is the biggest connoisseur of rumors about the girls of Gensokyo among the tengu. Her intelligence gathering abilities are the best in Gensokyo!

During the coming n days, Aya is planning to take many photos of m cute girls living in Gensokyo to write Bunbunmaru News daily and record at least Gx photos of girl x in total in the Bunkachou. At the k-th day, there are Ck targets, Tk1, Tk2, …, TkCk. The number of photos of target Tki that Aya takes should be in range i>Lki, Rki, if less, Aya cannot write an interesting article, if more, the girl will become angry and use her last spell card to attack Aya. What’s more, Aya cannot take more than Dk photos at the k-th day. Under these constraints, the more photos, the better.

Aya is not good at solving this complex problem. So she comes to you, an earthling, for help.

Input

There are about 40 cases. Process to the end of file.

Each case begins with two integers 1 <= n <= 365, 1 <= m <= 1000. Then m integers, G1, G2, …, Gm in range [0, 10000]. Then n days. Each day begins with two integer 1 <= C <= 100, 0 <= D <= 30000. Then C different targets. Each target is described by three integers, 0 <= T < m, 0 <= L <= R <= 100.

Output

For each case, first output the number of photos Aya can take, -1 if it’s impossible to satisfy her needing. If there is a best strategy, output the number of photos of each girl Aya should take at each day on separate lines. The output must be in the same order as the input. If there are more than one best strategy, any one will be OK.

Output a blank line after each case.

Sample Input

2 3
12 12 12
3 18
0 3 9
1 3 9
2 3 9
3 18
0 3 9
1 3 9
2 3 9

2 3
12 12 12
3 18
0 3 9
1 3 9
2 3 9
3 18
0 0 3
1 3 6
2 6 9

2 3
12 12 12
3 15
0 3 9
1 3 9
2 3 9
3 21
0 0 3
1 3 6
2 6 12

Sample Output

36
6
6
6
6
6
6

36
9
6
3
3
6
9

-1

解题思路

这是一个有源汇有上下界的网络流,将下界处理后跑网络流就能解决,先说一下怎么建图。

源点S每一天建立有向边,边权为该天拍照数量的上限Di,下界为0;每个女神向汇点T建立下界为Gi的上界为无穷大的有向边;接下来就是每天给每个女神拍照的边了,n天每天Cj个女神,天的编号i为1到n,女神的编号k为n+1到n+m,注意读入数据女神编号从0开始编号,加n+1就能转成n+1到n+m了,根据输入数据建立i到k的边,下界为x上界为y。建图大概如此,如何解决有源汇有上下界的网络流呢?

首先转成无源汇,建立一条T到S的下界为0上界为无穷大的有向边,这样就无源点汇点了,而且建立这一条边并不影响流量平衡,因为S流出量跟T流入量是相等的,原图只是转换成循环流而已。上一篇文章已经讲过,无源汇有上下界的网络流怎么解决了:建立超级源点SS和超级汇点TT,统计每个点下界流入量之和(含流出量),如果是正的,SS流入到该点,如果是负的,那么该点流出到TT,对于原来有上下界的边,全部转成上界为y-x,下界为0的边,因为x是必须流,有SS→TT解决了。

如果SS→TT的最大流等于正的流入量之和,那么说明存在可行流。可行流可能不是最大流,那我们就保证下界的情况下在进行S到T的增广:SS和TT用来判断可行流,用完之后删掉他,让h[SS]=h[TT]=0,这样到了这两个点就不会继续流了,原来的必须流还是必须流。跑完S→T的最大流之后,最大拍照数量就是S反向边流量之和(S不会流向SS和TT),或者是天流向人的反向边流量之和,还可以是后面重新跑最大流的流量,为什么呢?前面S不是可能有流量流出吗?这样不会算少了S的流出量吗?因为即使前面S有流量流出,也是T→S的流量,在跑一次网络流,这部分流量可以通过反向边S→T算回来。

程序实现

代码41行,如果s为0,说明有流量w到a,a也无法增广,下次就不需要再过来了,将v[a]改成0,就不会满足v[b]==v[a]+1的条件,从而实现了剪枝,避免了大量重复搜索,也避免了超时。

代码77到81行,枚举所有反向边(奇数),如果终点b是天,那么b必定在1到n范围,即小于等于n,且起点一定不是天;如果起点a是人,那么a范围必定在n+1到n+m,即小于等于n+m,之所以不判断大于n,是因为不可能a和b都是天、都小于等于n。

下面同样是Dinic算法,与上面不同的是,上面bfs一次后,通过dfs可以增广多次,但dfs的时间复杂度并不稳定,可能出现一条路走很多次的情况,或者说每次增广流量比较小。下面的代码,一个点可以多次访问,但每条边就只能访问一次,int &i=h[a],i变了之和,h[a]也跟着变化,如果下次再进入这个点,前面访问过的边就不会再走了,因为h[a]已经改变了,这样就保证了每条边只访问一次,bfs一次后,即使多次dfs,多次dfs的复杂度也只是O(m+n),因为每条边只走一次。

两种方法结合在一起行不行?每条边只访问一次,dfs一次多次增广?不妥!因为dfs的流量会越来越少,可能导致后面即使有大容量的边,也只能增广一点点。

[上下界最大流]ZOJ3229ShoottheBullet:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!