问题重述

奶牛们模仿美国州际公路系统的建设者，引入了"Interpasture Path"编号系统。他们已经将 N（2 ≤ N ≤ 25）个牧场编号为 1 到 N，并为连接两个牧场的每条路径分配了一个唯一的编号，范围在 1 到 2000 之间（例如 I-9 和 I-16）。

给定一个牧场和路径的连通图，贝茜喜欢从牧场 1 走到牧场 2，且不重复访问任何牧场。对于每条可能的路径，她会计算所经过路径编号的最大公约数（GCF）。最后，她会将所有路径的 GCF 的最小公倍数（LCM）计算出来。

输入格式

• 第一行：N（牧场数量）
• 接下来的 N 行：表示牧场的对称连通矩阵。第 L 行表示牧场 L-1 与其他牧场的连接情况，其中第 i 个数字表示连接牧场 L-1 和牧场 i 的路径编号（0 表示没有路径）。

输出格式

• 一行：所有可能路径的 GCF 的 LCM。

示例输入

4
0 0 3 16
0 0 9 6
3 9 0 0 
16 6 0 0

示例输出

6

解题思路

这道题目要求我们计算从牧场1到牧场2所有可能路径的路径编号的最大公约数(GCF)的最小公倍数(LCM)。我们需要考虑以下几点：

1. 路径定义：路径不能重复访问任何牧场
2. GCF计算：对于每条路径，需要计算路径上所有边编号的GCF
3. LCM计算：最后需要计算所有路径GCF的LCM

题意分析

1. 输入格式：

   • 第一行是牧场数量n
   • 接下来n行是邻接矩阵，表示牧场间的连接关系

2. 特殊处理：

   • 题目中将0值替换为1（因为0不能参与GCF计算）
   • 使用动态规划的思想，通过三重循环计算所有可能的路径

3. 算法选择：

   • 使用Floyd-Warshall算法的变种来计算路径的GCF
   • 通过动态规划的方式逐步构建路径的GCF信息

算法标签

• 动态规划
• 图论
• 最大公约数(GCD)
• 最小公倍数(LCM)
• Floyd-Warshall算法

代码分析

1. 输入处理：

   • 读取牧场数量n
   • 读取邻接矩阵，并将0值替换为1

2. 动态规划计算：

   • 使用三重循环(k,i,j)来更新路径信息
   • 对于每对牧场(i,j)，考虑通过中转牧场k的路径
   • 更新规则：mp[i][j] = mp[i][j] * gcd(mp[i][k], mp[k][j]) / gcd(mp[i][j], gcd(mp[i][k], mp[k][j]))

3. 输出结果：

   • 直接输出mp[1][2]，即牧场1到牧场2的路径信息

代码解释

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn=25+5;
int n,mp[maxn][maxn];

// 计算最大公约数
inline int gcd(int x,int y){
    return y==0?x:gcd(y,x%y);
}

signed main(void){
    // 输入处理
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            scanf("%lld",&mp[i][j]);
            if(mp[i][j]==0)
                mp[i][j]=1; // 将0替换为1
        }
    
    // 动态规划计算路径信息
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(mp[i][k]&&mp[k][j])
                    // 更新路径的GCF信息
                    mp[i][j]=mp[i][j]*gcd(mp[i][k],mp[k][j])/gcd(mp[i][j],gcd(mp[i][k],mp[k][j]));
    
    // 输出结果
    cout<<mp[1][2]<<endl;
    return 0;
}

复杂度分析

1. 时间复杂度：

   • 三重循环导致时间复杂度为O(n^3)
   • 对于n≤25的情况完全可接受

2. 空间复杂度：

   • 使用邻接矩阵存储图信息，空间复杂度为O(n^2)