1548: 旅行

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：8 解决：15

题目描述

lcl打算去n个城市旅行，他的预算是W
城市编号从1-n,城市之间两两可达
城市u到城市v的花费为w[v]
lcl从城市1出发，他的目标是除了出发的城市外，每个城市都到达并且只到达一次，在最后回到出发的城市，并且恰好用完预算，求一共有多少种不同的旅行方案
保证至少有一个解

输入

第一行两个整数n,W代表共有n个城市和lcl的预算W
接下来给出一个n*n的矩阵w，w[i][j]代表城市i到城市j的花费
1 <= n <= 8
1 <= W <= 1e9
如果i = j
w[i][j] = 0
否则
1 <= w[i][j]=w[j][i] <= 1e8

输出

一个整数，代表满足条件的方案数

样例输入 复制 

5 29
0 5 9 2 7
5 0 2 10 6
9 2 0 6 10
2 10 6 0 9
7 6 10 9 0

样例输出 复制 

4

提示

满足条件的路径
1 -> 2 -> 3 -> 4 -> 5 -> 1 
1 -> 2 -> 5 -> 3 -> 4 -> 1 
1 -> 4 -> 3 -> 5 -> 2 -> 1 
1 -> 5 -> 4 -> 3 -> 2 -> 1

来源/分类