作者RockLee (Now of all times)
看板Prob_Solve
标题[问题] Google Code Jam 2009, Round 3 - C
时间Thu Mar 15 18:26:39 2012
题目叙述网址:
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,
小弟是否哪边误解了呢?
麻烦版上高手开示一下 3-colorable 如何判断 <_.._>
[Invader's solution in Java]
import java.io.*;
import java.util.*;
public class C implements Runnable
{
private String IFILE = "C-large-practice.in";
private Scanner in;
private PrintWriter out;
private class Pset implements Comparable<Pset>
{
int x;
int y;
public Pset(int x, int y)
{
this.x = x;
this.y = y;
}
public int compareTo(Pset o)
{
return o.x - x;
}
@Override
public String toString()
{
return "(" + x + ", " + y + ")";
}
}
public void Run() throws IOException
{
in = new Scanner(new File(IFILE));
out = new PrintWriter("output.txt");
int ntest = in.nextInt();
for (int test = 1; test <= ntest; test++)
{
int n = in.nextInt();
Pset[] mas = new Pset[n];
for(int i = 0; i < n; i++)
{mas[i] = new Pset(in.nextInt(), in.nextInt());}
Arrays.sort(mas);
int[] pru = new int[n];
int[] pr = new int[n];
int[] prd = new int[n];
Arrays.fill(pru, -1);
Arrays.fill(pr, -1);
Arrays.fill(prd, -1);
int result = 1;
for (int i = 0; i < n; i++)
{
for(int j = i - 1; j >= 0; j--)
if (mas[i].y - 1 == mas[j].y)
{
pru[i] = j;
result = 2;
break;
}
for(int j = i - 1; j >= 0; j--)
if (mas[i].y == mas[j].y)
{
pr[i] = j;
result = 2;
break;
}
for(int j = i - 1; j >= 0; j--)
if (mas[i].y + 1== mas[j].y)
{
prd[i] = j;
result = 2;
break;
}
}
for (int i = 0; i < n; i++)
if (pr[i] >= 0)
{
int f1 = i;
int f2 = pr[f1];
if (pru[f1] >= 0 && pru[f2] >= 0 && pru[f1] == pru[f2] ||
prd[f1] >= 0 && prd[f2] >= 0 && prd[f1] == prd[f2] ||
pru[f1] >= 0 && prd[pru[f1]] == f2 ||
prd[f1] >= 0 && pru[prd[f1]] == f2)
{
result = 3;
break;
}
}
for(int i = 0; i < n; i++)
if (pr[i] >= 0 && pr[pr[i]] >= 0)
{
int f1 = i;
int f2 = pr[f1];
int f3 = pr[f2];
if (pru[f1] == -1 || prd[f1] == -1) continue;
if (pru[f2] == -1 || prd[f2] == -1) continue;
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;
}
}
out.println("Case #" + test + ": " + result);
}
in.close();
out.close();
}
public void run()
{
try {Run();}
catch(IOException e) {}
}
public static void main(String[] args) throws IOException
{
new C().Run();
}
}
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 59.126.30.95