问题 1088. -- 【基础图论】哈密顿路问题

1088: 【基础图论】哈密顿路问题

时间限制: 15 Sec  内存限制: 128 MB
提交: 25  解决: 10
[提交][状态][讨论版]

题目描述

邮递员在送信时,为了节省路途,自己规定:每次总是从n个村子中选择其中一个合适的村子出发,途经每个村子仅且经过一次,送完所有的信。 已知各个村子的道路连通情况。请你帮邮递员选择一条合适的路线。

输入

第1行:整数n(2<=n<=200):村子的个数。

接下来是一个n*n的0、1矩阵(每2个数之间有1个空格),表示n个村子的连同情况,如:a[i,j]=1 ,表示第i和第j个村子之间有路可走,如果a[i,j]=0,表示他们之间无路可走。

输出

第1行:1个整数表示可行的方案总数。

样例输入

7 
0 1 0 1 1 0 0 
1 0 1 0 1 0 0 
0 1 0 0 0 0 1 
1 0 0 0 0 0 0 
1 1 0 0 0 1 0 
0 0 0 0 1 0 1 
0 0 1 0 0 1 0 

样例输出

8

提示

来源

[提交][状态]