Noi模拟 弹球游戏 费用流

弹球游戏(bounce)

【题目描述】

妹老师引进了一个新的弹球游戏,游戏区域是一个n*m的网格,格子坐标编号从(1,1)到(n,m),每个格子里都有一个斜面,斜面有四种摆放方式:

//此处自行YY四个正方形,分别被黑白分成两半,一半是一个等腰三角。

 

灰色是墙壁白色是空地,球碰到斜面会反弹。

玩家可以选择任何一个格子的中心,向上下左右四个方向之一扔出一颗弹球,弹球会在网格中反复碰撞走出一条路径。弹球不允许与灰色部分两条直角边以及边界碰撞。

例如出现如下碰撞情况玩家直接失败:

可以证明满足条件的路径,最终一定会回到发射点。

同时,初始时刻每相邻两个格子之间都有一面很薄的墙壁,弹球可以穿过并击碎它,击碎会带来收益(可正可负)。Cij表示击碎(i,j)和(i,j+1)之间的墙壁的收益,Rij表示击碎(i,j)和(i+1,j)之间的墙壁的收益。

除此之外,妹老师还设置了K个特殊格子,它们的中心必须被经过至少一次,否则游戏算作失败。

假老师可以任意安排每个格子里斜面的摆放方式,并且可以在任意一些格子中心扔出任意多个弹球,他想知道他能获得的最大收益是多少(为了使游戏不失败,收益可能为负)。

有多组数据

【输入数据】

第一行一个整数T表示数据组数。

对于每组数据:

第一行两个整数n,m表示网格边长,接下来n行每行m-1个整数表示Cij,接下来n-1行每行m个整数表示Rij。

接下来一行一个整数K表示特殊格子数量,接下来K行每行两个整数Xi,Yi表示特殊格子坐标。

【输出数据】

每组数据输出一行一个整数表示最大收益,若游戏必然失败输出Impossible。

【样例输入】

2

4 4

0 0 -1

0 1 0

0 -1 -1

0 1 0

1 0 1 0

-1 -1 0 0

1 1 -1 -1

1

3 3

2 3

0 0

0 0

0 0 0

2

1 1

2 3

【样例输出】

2

Impossible

【数据范围】

subtask1[9pts]:nm<=10。

subtask2[11pts]:nm<=20。

subtask3[20pts]:Rij=Cij=0。

subtask4[22pts]:K=0。

subtask5[15pts]:n,m<=10。

subtask6[23pts]:无特殊条件。

对于全部数据,1<=T<=50,1<=n,m<=30,|Cij|,|Rij|<=500,0<=K<=100,1<=Xi<=n,1<=Yi<=m。

////////////////////////////////////////////////////////////////////////////////////////////////////////

这题考场上一脸懵逼,生无可恋,完全不会,woc!什么都不告诉你,怎么做,,QwQ。。。

看了题解感觉好神,这种题竟然还可以用网络流,完全看不出来啊。

我们考虑我们将图黑白染色,我们的球必然在黑格子上下移动,白格子左右移动。这非常显然,因为每个格子都得放个三角障碍物,想移动就必然得这样子弯曲着前进。你可能会问,为什么要钦点黑色上下,白色左右,可能存在一种情况在黑色左右,白色上下呢?显然我这么钦点没有问题,因为交换黑白的移动方式无非就是一个圈的正逆走法不同而已。

我们考虑,最终的合法路径无非就是出度等于入度且不超过1。需要限制度,我们又考虑到这是黑白棋盘染色,极有可能是跟网络流,匹配之类的相关。我们考虑我们建一个源,建立一个汇。然后一列点表示出点,一列点表示入点。我们源连到左列点,右列点连到汇。然后我们考虑,对于一个格子,如果其必须走,那么意味着他必定会从别的格子的出点走来,走到别的格子的入点对吧。那我们对于非必须走的点出入点之间连(1,0)的边。而必须走的格子就不连这个,迫使他走出一个回路。而不在回路上的点顺着出入点之间的边就走掉了,也不会影响结果。我们考虑一个格子,我们应该从他连边到周围能到达的格子,那么流量显然还是1,费用呢,显然是打破边界的收益。这样子我们只要做最大费用最大流就可以了。如果最后流< n * m 那么就意味着有些必须走的格子最后没走成,就没有方案。否则就是此时的费用咯!

 

发表评论