主页 / 问题 / 1415293
Accepted
VIctor
Asked:2022-07-30 23:21:11 +0000 UTC2022-07-30 23:21:11 +0000 UTC

如何加快图的最优性检查？

  • 772

大家好。这里有一个问题：X 国有 n 个城市，它们被分配了从 1 到 n 的数字。该国的首都编号为 n。铁路铺设在城市之间。

但是，根据画布的宽度，道路可以分为两种类型。任何火车只能在一种轨道上行驶。传统上，一种道路标记为R，另一种道路标记为B。也就是说，如果从一个城市到另一个城市的路线同时具有R类道路和B类道路，则没有火车能够沿着该路线通过。从一个城市到另一个城市，您只能在仅由 R 类道路或 B 类道路组成的路线上行驶。

但这还不是全部。在 X 国的道路上，您只能从编号较低的城市移动到编号较高的城市。这解释了居民大量涌入首都的原因，首都的数量为 n。

如果没有一对城市 A 和 B 使得从 A 到 B 可以通过类型 R 的道路和类型 B 的道路到达，则铁路地图被称为最优。换句话说，对于任何一对城市，它是确实，从数量较少的城市到数量较多的城市，只能通过一种类型的道路到达，或者根本无法建造路线。看看给你的卡是否是最佳的。

那么，那么这些R和B路就设置好了。我正面解决了，也就是我傻傻的找到了从顶点1到N的所有路径，发现那里只有一种路。但是已经在 25 个城市中，一切都运行得非常长。我知道有一些更简单的算法，但没有想到。给我一些想法，以哪种方式思考？

графы

3 个回答

  1. 构建两个单独的图，R 和 B。对于每个通过广度优先遍历（或任何其他方式），构建一个连通性表，其中A[i,j]=0fori<j表示路径 from itoj不存在，并且A[i,j]=1- 存在

    对两个表的对应元素进行 AND 运算。如果结果仅包含零，则映射是最优的。

    • 0
  2. Best Answer

    翻转图的所有边B并与图的边混合R。在生成的一般有向图中寻找循环。如果至少有一个，则地图不是最优的。

    R该解决方案的工作时间与和中的总边数成正比B。

    • 0

  3. 这就是一切的运作方式。谢谢大家！

    static void dfs(int v)
        {
            if (flag == 1) return;
            visited[v] = 1;
    
            for (int i = 0; i < inpArrayGraph[v].size(); i++)
            {
                int to = inpArrayGraph[v].get(i);
                if (visited[to] == 1)
                {
                    flag = 1;
                    return;
                }
                else if (visited[to] == 0) dfs(to);
                if (flag == 1) return;
            }
            visited[v] = 2;
        }
    • 0

相关问题