GCC版本升级到4.9.2,大家再也不用因为头文件而导致本地编译通过而网站通不过了。fpc版本为2.6.4。Java版本为1.8.0_45。

问题 1060. -- 【基础】四色定理

1060: 【基础】四色定理

时间限制 : 1 Sec
内存限制 : 16 Mb
提交 : 2369
解决 : 1510

题目描述

著名的四色定理你一定听说过吧?这可是近代世界三大数学难题之一唷(顺便提上一句,另外两个是费马定理和哥德巴赫猜想)。

四色定理的提出来自英国。1852年,毕业于伦敦大学的弗南西斯•格思里(Francis Guthrie)在一家科研单位搞地图着色工作时,发现了一种有趣的现象:“看来,每幅地图都可以用四种颜色着色,使得有共同边界的国家着上不同的颜色。”(注意:只要求有公共边的区域不同色就可以,只有公共顶点的同色也没关系)这个结论能不能从数学上加以严格证明呢?他和在大学读书的弟弟格里斯决心试一试。兄弟二人为证明这一问题而使用的稿纸已经堆了一大叠,可是研究工作没有进展。

1852年10月23日,他的弟弟就这个问题的证明请教他的老师、著名数学家德•摩尔根,摩尔根也没有能找到解决这个问题的途径,于是写信向自己的好友、著名数学家哈密尔顿爵士请教。哈密尔顿接到摩尔根的信后,对四色问题进行论证。但直到1865年哈密尔顿逝世为止,问题也没有能够解决。

直到1976年,在J. Koch的算法的支持下,美国数学家阿佩尔(Kenneth Appel)与哈肯(Wolfgang Haken)在美国伊利诺斯大学的两台不同的电子计算机上,用了12个秒,作了1判断,才终于完成了四色定理的证明。

你的任务相对那些数学家们来说当然要容易得多:你只要编写一个程序,计算一下在给定的一张有200个区域的地图上,用四种颜色填充不同区域,并保证有公共边的区域不同色的方案数有多少就可以了。

 

输入

第一行是一个整数 N(0 ≤ N ≤ 10 ),分别表示地图中有公共边的区域的信息数量。

下面 N 行,每行一对整数,表示对所有区域编号之后,此两个编号的区域是有公共边的。

 

输出

只有一个整数,表示用四种颜色填充地图的总方案数。注意,在某些方案中,所有四种颜色不必都用到。

 

样例输入 [复制]

4 1 2 1 3 1 4 1 5

样例输出 [复制]

324

提示[+]

*** 提示已隐藏,点击上方 [+] 可显示 ***

来源

2008年北京市小学生邀请赛模拟题(5)


Problem 1060
全 屏
重置代码