注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

vfleaking的博客

My name is VFlea King

 
 
 

日志

 
 

SRM 558 Div1 1000pts 题解  

2012-10-28 23:37:07|  分类: Topcoder |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
题目
【Problem Statement】
Surrounding Game is a single-player game played on a rectangular grid of cells. Cells are considered adjacent if they share a common side. (Hence, each cell has at most four adjacent cells. The cells on the sides and in the corners of the grid have fewer adjacent cells than the ones inside the grid.)

The game is played by placing stones into some of the cells. Each cell may only contain at most one stone. A cell is called dominated if at least one of the following two conditions holds:
The cell contains a stone.
All cells adjacent to the cell contain stones.

Each cell of the grid contains two numbers, each from 0 to 61, inclusive: the cost of placing a stone into the cell, and the benefit from dominating the cell. At the end of the game, the overall score of the player is the sum of all benefits minus the sum of all costs.

You are given the vector <string>s cost and benefit. The characters cost[i][j] and benefit[i][j] represent the two numbers written in the cell (i,j), using the following encoding:
Characters '0'-'9' represent numbers 0-9.
Characters 'a'-'z' represent numbers 10-35.
Characters 'A'-'Z' represent numbers 36-61.

For example, if character 7 of element 4 of cost is 'B', the cost of placing a stone into the cell (4,7) is 37. 

Calculate and return the maximal possible score for the given grid.

【Definition】
Class:SurroundingGame
Method:maxScore
Parameters:vector <string>, vector <string>
Returns:int
Method signature:int maxScore(vector <string> cost, vector <string> benefit)
(be sure your method is public)


【Constraints】
cost will contain between 2 and 20 elements, inclusive.
cost and benefit will contain the same number of elements.
Each element of cost will contain between 2 and 20 characters, inclusive.
Each element of cost will contain the same number of characters.
Each element of benefit will contain the same number of characters as element 0 of cost.
Each character in cost and benefit will be a character from '0'-'9','a'-'z', or 'A'-'Z'.

Topcoder官方题解的翻译
blue.boy 花了大约30分钟时间来解决这个问题但是我不得不花大量时间来理解他的解法(多谢rng_58)。这个想法是建立一个最小割代表着在网格中放置石子的方案的网络流。首先,把所有格子的 benefit 值和我们能从这个格子获得的价值加起来(比如,对于格子cell(r, c),我们应该往总和中加入这么多:benefit(r, c) + max(0, benefit(r, c) - cost(r, c))),用一个变量存下这个值,命名为SUM。把所有格子分成两组,第一组包括所有(r + c) % 2 = 1的格子cell(r, c),把这一组的格子全部染成黑色,另一组全部染成白色。每个格子有一个唯一与之对应的虚拟格子,令v_cell(u, v)是与cell(u, v)对应的虚拟格子。把虚拟格子染成与对应的格子相同的颜色。每个格子(包括虚拟格子)都是网络流的一个结点,现在我们来添加边。
首先这里有一些流量为无穷大的边:
对于黑格子,v_cell(u, v) 向 cell(u, v)连边;对于白格子,cell(u, v) 向 v_cell(u, v)连边。
如果黑格子cell(u, v) 和 白格子cell(r, c)是相邻的,就添加两条边:从cell(u, v) 到 v_cell(r, c)和从v_cell(u, v) 到  cell(r, c)。
事实上我们添加上述这些边是为了避免某两个格子以某种特定模式出现在最小割中。举例来说,如果最小割容量是有限的并且黑格子是在S割(被最小割切割后包括源的那个顶点集合)中的,那么与它相邻的白格子也一定会出现在S割中。当然了,我们还需要更多的边。
从原点向黑格子v_cell(u, v)连一条容量为benefit(u, v)的边。
从白格子v_cell(u, v)向汇点连一条容量为benefit(u, v)的边。(汇点的英文居然是terminal!! ————译者)
设T = benefit(u, v) - cost(u, v)
如果cell(u, v)为黑,那么源点向cell(u, v)连一条容量为max(0, -T)的边,cell(u, v)向汇点连一条容量为max(0, T)的边
如果cell(u, v)为白,那么源点向cell(u, v)连一条容量为max(0, T)的边,cell(u, v)向汇点连一条容量为max(0, -T)的边
现在你只需要找到最小割的容量然后用SUM减去它就能得到答案。

最困难的部分就是弄懂为什么这个算法是对的?事实上,你找到最小割之后,我们应该放石子的格子就是那些所有自己连同对应的虚拟格子一起属于T的黑格子和那些自己连同对应的虚拟格子一起所有属于S的白格子。如果一个黑格子连同对应的虚拟格子属于S,那么我们不应该往这个格子里放石子但是cell(u, v)会成为dominated cell。类似地,如果一个白格子连同对应的虚拟格子属于T,那么我们不应该往这个格子里放石子但是cell(u, v)会成为dominated cell。对于其他情况,cell(u, v)不是dominated cell。
明白了表示石子的方式之后,证明算法就不是很难了,虽然证明很长。关键就是最小割容量是有限的(看看连接汇点和源点的边的容量总和)。
现在来证明其中的一部分,对于一个黑格子cell(u, v),如果它和它的虚拟格子是属于S割的,那么对于每个与它相邻的白格子cell(r, c),cell(r, c) 和 v_cell(r, c)也会在S割中(看看(cell(u, v),v_cell(u, v))和(cell(r, c), v_cell(r, c))之间的连边)。在这种情况下,cell(u, v)所有相邻格子都包含了一个石子,是dominated cell(虽然没有包含一个石子)。观察cell(u, v),它对SUM的贡献为benefit(u, v) + max(0, benefit(u, v) - cost(u, v)),对最小割容量的贡献为max(0, benefit(u, v) - cost(u, v))(这个值为从cell(u, v)连向汇点的边的容量)。于是cell(u, v)对答案的贡献为benefit(u, v)(这是合理的,因为cell(u, v)是个dominated cell但是不包括一个石头)。继续进行相似的证明(事实上还有5种情况),我们将会容易明白这个方法的正确性,也会明白这个问题是多么难。

一道网络流最小割的好题,给blue.boy跪烂 ————译者

【疑点】
对于其他情况,cell(u, v)不是dominated cell。”,啥是其他情况?求大神解答。
其它情况是指,举例来说,黑格子cell(u, v)属于T割时,尽管cell(u, v)有容量为无穷大的边连向v_cell(u, v),但是v_cell(u, v)仍然可能在S割。对于这种情况,该格子就不是dominated cell。
  评论这张
 
阅读(1134)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017