完全回路加强版

题目描述:

给出一个完全的有向图，求一条除起点外（最终回到起点）经过且仅经过每个顶点一次的路径，使得经过的权值最大。

输入格式:

第一行 n

以下一个n*n的矩阵

第i行第j列表示从点i到点j有一条路。

输出格式:

共n+2行

第一行 最大的权值

以下n+1行 输出路径 若存在多条路径 输出字典序列最小的。

样例输入:

3
0 10 30
30 0 30
50 30 0

样例输出:

90
1
2
3
1

提示:

N<=15

时间限制: 1000ms
空间限制: 256MB

---