作者ledia (下班後才下棋)
站内Prob_Solve
标题Re: [问题] Google Code Jam 2009, Round 3 - C
时间Thu Mar 15 22:39:53 2012
※ 引述《RockLee (Now of all times)》之铭言：
: 题目叙述网址:
: http://code.google.com/codejam/contest/243103/dashboard#s=p2
: 没有想出来如何判断是否为 3-colorable,
: 看了当初参赛者上传的 code 还是不太懂 ~><~
: Invader 的 code 中用来判断是否为 3-colorable 主要为以下几行:
: int count = 0;
: int u = pru[f1];
: while (u != pru[f2]) {u = pr[u]; count++;}
: int d = prd[f1];
: while (d != prd[f2]) {d = pr[d]; count++;}
: if (count % 2 == 1) {result = 4; break;}
: 看起来的意思似乎是, 若同一列的两个相邻球员间,
: 前一列在这两个相邻球员间的人数与後一列在这两个相邻球员间的人数和为奇数,
: 则非 3-colorable.
: 但我不懂的是为何这样就可确认非 3-colorable, 例如以下三列(数字代表颜色):
: _1_2_1_
: 2_____0
: __1_2__
不能够 3-colorable
除了 (count % 2 == 1) 之外,
还有几个条件:
1. pru[f2] != -1, prd[f2] != -1
2. pr[f2] != -1
所以图应该要是底下这样的
pru[f2]->x, prd[f2]->z, pr[f2]->y
_1_2_1_x
2_____0___y
__1_2___z
试图用 3 colors, x->2, z->1, y 就不行了
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.30.33
※ 编辑: ledia 来自: 140.112.30.33 (03/15 22:40)
1F：推 RockLee:感谢 L 大的解释~ 03/15 23:26