关于 Hamilton路径
由天文学家哈密顿提出,定义:G=(V,E)是一个图,若G中一条路径通过且仅通过每一个顶点一次,称这条路径为哈密顿路径。若G中一个回路通过且仅通过每一个顶点一次,称这个环为哈密顿回路。若一个图存在哈密顿回路,就称为哈密顿图。
这题说的就是哈密顿路径。
主体思路
dp[i][j] : 所有从0走到 j , 走过的所有点是 i 的所有路径
动态转移方程:dp[i][j] = min(dp[i][j], dp[i - (1 << j)][k] + grep[k][j])
注意细节
【二进制表示】
比如有 0-4 共5个点,用一个数来表示访问了0,2,3,4这四个点,这样表示:11101
表示访问了0,2,4这三个点,这样表示:10101
用 (x >> n) & 1
来访问 x 在第 n 位上是 0 还是 1
【go语言细节】
又看到大数,使用 bufio + os 快读保险一点
更新:后来又试了用一般输入来做,也能过
【dp空间的初始值】
看过老师的代码,会知道他给dp空间初赋值为0x3f
在C++,是一个极大的数,是1061109567 ,是10^9级别的。老师这样写是完全没问题的。
但在go语言上,0x3f
就会成为 63
,从而导致计算错误
可以用 math包
的 math.MaxInt32 >> 1
(1073741823)
又或者直接 1 << 31 - 1
(2147483647)
基础代码
package main
import (
"bufio"
"fmt"
"os"
)
func cal(n int, grep [][]int) int {
min := func(i, j int) int { if i < j { return i }; return j }
m := 1 << n
dp := make([][]int, m)
for i := range dp {
dp[i] = make([]int, n)
for j := range dp[i] { dp[i][j] = 1 << 31 - 1 }
}
dp[1][0] = 0
for i := 1; i <= 1 << n; i++ {
for j := 0; j < n; j++ {
if (i >> j) & 1 > 0 {
for k := 0; k < n; k++ {
if (i >> k) & 1 > 0 { dp[i][j] = min(dp[i][j], dp[i ^ (1 << j)][k] + grep[k][j]) }
}
}
}
}
return dp[(1 << n) - 1][n - 1]
}
func main() {
var (
in = bufio.NewReader(os.Stdin)
n, tmp int
)
fmt.Scanf("%d", &n)
grep := make([][]int, n)
for i := range grep { grep[i] = make([]int, n) }
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
fmt.Fscan(in, &tmp)
grep[i][j] = tmp
}
}
fmt.Printf("%d", cal(n, grep))
}
用一般输入做的
和用bufio做好像也没多大差距......
上面的是一般输入,下面的是用了bufio
package main
import "fmt"
func cal(n int, grep [][]int) int {
min := func(i, j int) int { if i < j { return i }; return j }
m := 1 << n
dp := make([][]int, m)
for i := range dp {
dp[i] = make([]int, n)
for j := range dp[i] { dp[i][j] = 1 << 31 - 1 }
}
dp[1][0] = 0
for i := 1; i <= 1 << n; i++ {
for j := 0; j < n; j++ {
if (i >> j) & 1 > 0 {
for k := 0; k < n; k++ {
if (i >> k) & 1 > 0 { dp[i][j] = min(dp[i][j], dp[i ^ (1 << j)][k] + grep[k][j]) }
}
}
}
}
return dp[(1 << n) - 1][n - 1]
}
func main() {
var n int
fmt.Scanf("%d", &n)
grep := make([][]int, n)
for i := range grep { grep[i] = make([]int, n) }
for i := 0; i < n; i++ {
for j := 0; j < n; j++ { fmt.Scanf("%d", &grep[i][j]) }
}
fmt.Printf("%d", cal(n, grep))
}