2

这是问题链接：http ://codeforces.com/contest/295/problem/B

Greg 有一个加权有向图，由 n 个顶点组成。在此图中，任何一对不同的顶点在它们之间在两个方向上都有一条边。Greg 喜欢玩图表，现在他发明了一个新游戏：

游戏由 n 个步骤组成。在第 i 步，Greg 从图中删除了顶点号 xi。当 Greg 删除一个顶点时，他也删除了所有进出该顶点的边。在执行每一步之前，Greg 想知道所有剩余顶点对之间最短路径的长度总和。最短路径可以通过任何剩余的顶点。帮助 Greg，在每一步之前打印所需总和的值。

输入：

第一行包含整数 n (1 ≤ n ≤ 500) — 图中的顶点数。

接下来的 n 行每行包含 n 个整数 — 图邻接矩阵：第 i 行中的第 j 个数 aij (1 ≤ aij ≤ 105, aii = 0) 表示从顶点 i 到顶点 j 的边的权重.

下一行包含 n 个不同的整数：x1, x2, ..., xn (1 ≤ xi ≤ n) — Greg 删除的顶点。

输出：

打印 n 个整数——第 i 个数字等于第 i 步之前所需的总和。

因此，基本上我的方法是在删除任何顶点之前运行 Floyd-Warshall 算法，对于删除，我只需将要删除的顶点的值设置为INT_MAX行和列中的邻接矩阵中的值。

基本上，这个循环在main

    for (int h = 0; h < n; h++)
    {
        func();
        int val = arr[h];   // arr contains the vertices to be deleted
        for ( i = 1; i <= n; i++ )
            dist[val][i] = INT_MAX;
        for ( i = 1; i <= n; i++ )
            dist[i][val] = INT_MAX;
    }

这是我对 Floyd Warshall 算法的实现：

void func () 
{
    //int i,j,k;
    ans = 0;
    for ( i = 1; i <= n; i++ )
    {
        for ( j = 1; j <= n; j++ )
        {
            if (i == j)
                val[i][j][0] = 0;
            else if (dist[i][j] != 0)
                val[i][j][0] = dist[i][j];
            else
                val[i][j][0] = INT_MAX;
        }
    }
    for (k = 1; k <= n; k++)
        for ( i = 1; i <= n; i++ )
            for ( j = 1; j <= n; j++ )
                val[i][j][k] = min(val[i][j][k-1],val[i][k][k-1]+val[k][j][k-1]);   
    //int ans = 0;
    for ( i = 1; i <= n; i++ )
        for ( j = 1; j <= n; j++ )
            ans = ans + val[i][j][n];
    cout<<ans<<"\t";
}

这里，val是我制作的全局 3-D 矩阵，arr包含要删除的顶点。但是，当我运行此逻辑时，它仅在最初给出正确答案，即没有删除任何顶点。但在那之后，它给出了一个错误的值。我不明白为什么？我的逻辑不正确吗？

4

2 回答 2

1

看起来很奇怪的一件事是，最后你要计算所有剩余顶点对的总和，但你的循环只是在所有顶点上：

for ( i = 1; i <= n; i++ )
    for ( j = 1; j <= n; j++ )
        ans = ans + val[i][j][n];
于 2015-09-15T11:51:11.730 回答
0

这是错误的方式，会得到 TLE .... 按照这种方式

你应该牢记对弗洛伊德战争算法的良好理解。

首先让自己清楚然后来到这一点，在这个算法中，你可以以任何顺序设计你的中间元素（k）。所以这里有n个步骤，这意味着n个节点将以给定的顺序被删除……这意味着在这个给定的顺序中你可以设计你的中间元素..说给定的删除顺序集是[1、2、3]………………。 .

现在这意味着当 1 个顶点将被删除时，每对最短路径的总和。那么当 2 也被删除时，以此类推……</p>

现在这样想，当只认为没有 3 的所有顶点被删除时，这里使用 k(3) u 可以在只剩下 3 时求和，现在使 k 的值为 (2)，这意味着只剩下 2 和 3其他的现在被删除了求和……..所以如果你反转这个答案，当剩下 1 2 3 时，然后求和（没有删除顶点），然后 1 删除

这意味着只有 2 ， 3 是剩余的其他已删除使它们的总和......。

所以，如果你对弗洛伊德沃歇尔算法有好的想法，我认为这应该很清楚。

基于上述想法，我在这里的整洁和干净的解决方案

https://github.com/joy-mollick/Problem-Solving-Solutions/blob/master/Codeforces-B%20-%20Greg%20and%20Graph.cpp

于 2019-07-31T12:07:02.333 回答