pku 3422 Kaka's Matrix Travels

什么时候能出点真正的原创题.

这题可用网络流求解，但构图并不好想：（设取数的次数为k）

我们可以把每个方格看做一个点，第i行第j列的方格是(i-1)*m+j个点，但是在网络流中点是没有权值的，怎样把这些点的权值表达出来呢？我们可以想到拆点，就是将一个点一分为二，中间用一条容量为1的边相连，边上的权值就是点权，第i个点可以拆成第2*i和2*i+1个点，然后第1个点为源，第2*m*n+2个点为汇，这样点就构好了。接下来连边，首先从源向第1个方格的起始点连一条边，再从最后1个方格的终止点向汇连一条容量为k的边，然后从每一个方格的终止点向右边和下面（如果有的话）方格的起始点连一条容量为k的边。但是这样对了吗？还是不对，为什么呢，应为如果每个方格起始点和终止点那条边容量为1的话，代表它只能经过一次，可是实际上不只可以走一次，只是权值只能加1次罢了。这个问题应该怎么解决呢？其实我们只要从每个方格的起始点向右边和下面的方格的起始点连一条容量为k的边，这个其实就是跳过了这个方格的权值，这样构图就可基本可以解决了。然后只要套用最大费用最大流就可以了，至于细节部分自己想把。

以上可能杂乱无章，难以看懂，请多多包涵。

B-.--.-T

编译通过...

├ **测试数据 **01： 答案正确... 0ms

├ **测试数据 **02： 答案正确... 0ms

├ **测试数据 **03： 答案正确... 0ms

├ **测试数据 **04： 答案正确... 0ms

├ **测试数据 **05： 答案正确... 0ms

├ **测试数据 **06： 答案正确... 0ms

├ **测试数据 **07： 答案正确... 0ms

├ **测试数据 **08： 答案正确... 0ms

├ **测试数据 **09： 答案正确... 0ms

├ **测试数据 **10： 答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

设取了 k 次（k 取方格数）

下面用元组 (u, v, c, w) 表示 u->v，容量c，权值w

每个方格 u 对应两个点 u u'，建立边 (u, u', 1, value)

(u, u', k-1, 0)

若 v 在 u 右面或下面，(u', v, k, 0)

设左上角为 source，右下角为 sink

求 source -> sink 的最大费用最大流

在题目里面说什么记忆化超时,弄起来好象我们不会费用流似的......

网络流快很正常……最大流又不超过n

拆点+网络流?

noip应该不考网络流

全是费用流？没有人写DP吗？

KAKA‘s matrix travel……

水题~

费用流秒杀~

DP只是利用了列数很少吧~ 不优美~

拆点的最大费用最大流

记录号 Flag 得分 记录信息 环境 评测机 程序提交时间

R1534101 Accepted 100 From 453844077－

　 P1653 CPP Vijos Dragon 2009-9-16 9:10:35

From talent123

疯狂的方格取数 天才的talent 系列

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 9ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：9ms

暴力网络流。没想到这么快。。。。

实际上最后5个数据都是骗分的。。。因为n》=m。。 所以直接就可以输出所有数的总和了。。。ORZ

最大费用最大流？

先ORZ,有空再做

……

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 572ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：572ms

用 位运算 第5个ＡＣ oh Yaeh

不是网络流的题么...动态规划能做么...11维Dp?

(回放之Curimit大牛与本菜不可不说的秘密:

本菜: Curimit大牛 我最近有道题被VIJOS刷了下来 说是有重复题 给你看哈!

Curimit: (看了一会儿...抑或是发了一会儿呆)

本菜: 大牛~这道题是五取方格数哦~ 我用了个六维数组还是很慢的说~

Curimit: (神秘地)你做过一道题叫N取方格数吗?

本菜: (狂摇头+郁闷...) 咋做...

Curimit: 这道题么很简单的呀..就建个网络流就可以了吗...

(以下省略建图/解决 几K字)

(只见Curimit大牛滔滔不绝 本菜晕倒在地 口吐白沫...)

(回放结束))

很明显是费用流。。。。。某牛的臆想题，居然被人先出了

数据貌似有误，还是下次再传吧

的确是很裸的费用流

Orz Curimit 神牛...

六维数组内存怎么会够？

这题拆点随便连连就可以AC了，比dp想起来还简单。