1 条题解

  • 1
    @ 2023-10-21 11:02:04

    Floyd版动态规划

    具体代码参考P1027 题解。只需要把Floyd的转移方程换为
    \[ f[i, j, k] = f[i, j, k-1] \lor (f[i, k, k-1] \land f[k, j, k-1]) \]
    其中\(\lor\)表示或,\(\land\)表示与。

    代码为:

    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++) // i, j, k全部是从1~n
            for(int j=1;j<=n;j++)
                dis[i][j]=f[i][j] | (f[i][k] & f[k][j]);
    
  • 1

信息

ID
1028
难度
1
分类
图结构 | 平面图 点击显示
标签
递交数
0
已通过
0
通过率
?
上传者