三圈图的最小Hosoya指标的任务书.docx

三圈图的最小Hosoya指标的任务书
任务书：
三圈图指由三个互相连接的圆组成的连通图，如下图所示。
请你研究对于给定的三圈图，其最小Hosoya指标的计算方法。Hosoya指标是指该图的所有不同的简单环（包括图中的三个圈）的节点数和边数之和。例如，在下图中，共有7个简单环，它们的节点数和边数之和分别为：
1.3+2=5
2.3+2+3=8
3.3+3+3=9
4.3+4+3=10
5.3+4+2+3=12
6.3+4+3+3=13
7.3+4+3+2+3=15
因此，这个图的Hosoya指标为5+8+9+10+12+13+15=72。
请你设计算法，针对给定的三圈图，计算其最小Hosoya指标。你需要使用图的邻接矩阵来表示该图，并采用程序自动读取输入和输出结果的方式。
具体要求如下：
输入：
输入的第一行包括一个整数n(3≤n≤100)，表示三圈图中所有节点的个数；
接下来的n行，每行n个整数0或1，用空格隔开。第i行第j列的整数表示节点i和节点j之间是否有边相连。若相连则该值为1，否则为0。
输出：
输出单独一个整数，表示给定三圈图的最小Hosoya指标。
样例输入：
6
011000
101100
110110
011011
001101
000110
样例输出：
42
提示：
三圈图是一种特殊的图形式，由于这个图的边具有一定的规律，因此对于一个节点i和j之间的连接情况，有以下特点：
节点i,j分别代表三个圆上的节点，节点i在第一圆上，节点j在第二圆上，若二者之间连有一条边，则相应的第三个点k将在第三个圆上，且与字符i,j的位置相对；
多个匹配关系之间不会重叠；也就是说，节点i和j之间的连边，在第三个圆上只有唯一的节点与之对应。