1. POJ 3613

    题意:一个无向图,求从一个顶点到另一个顶点的恰好经过k条边的最短路径,可能有自环,无重边。

    分析:这个题其实就是矩阵乘法,用了dp的思想,dp[k][i][j]代表恰好经过k条边的i到j的最短路,那么dp[k][i][j]=min{dp[k-1][i][p]+g[p][j]}(其中g是原图)。可以用矩阵乘法来做,因为对于dp[k-1][i][j]来说,只要乘以一次原图矩阵,就相当于做了一次转移,得到的就是dp[k][][]矩阵。我想说这个题除了状态设计和floyd稍微沾了一点边之外,其他一点关系都没有了,竟然看到网上好多人用写floyd的循环顺序来写这个题,真是令人费解,这个题只是改了矩阵乘法的最内层,改变了矩阵乘法的运算规则,和floyd真的没关系啊!!!

    另外,矩阵乘法的规则和在图中求一个点到另一个点的恰好经过k条边的方法数的规则是一样的,二者的状态转移方程也是一样的,所以矩阵乘法不需要经过任何修改就能做这种求恰好经过k条边的方法数的题,而不用像这个题还得做些修改。这些题都需要注意初始化的东西 ...

  2. POJ 1734

    题意:一个无向图,所有边权为正,求这个无向图中的一个权值最小的环(环的权值定义为环中所有边权值的和)。要求环的顶点数至少为3个,且图中可能存在重边。

    分析:这个题我最开始只有搜索的想法,后来看到了floyd的做法,才折服了,向强大的floyd致敬! 这个题可以这么想,抛开floyd的思路,我们知道每个环中都有一个顶点标号最大的顶点(比如为k)。我们可以枚举这个顶点,枚举完这个顶点之后我们再枚举另外两个和它相邻的顶点i和j(i,j < k)。如果这个时候我们知道i到j的不经过k的最短路(设为p),那么我们就可以把边i->k,k->j和路径p组合起来,成为一个环,如果这个环的权值小于当前求出的所有环里面的最小权值的话,那么就更新一下最小值,并记录路径。

    恩,这个思路看上去是挺好的,但是我们怎么求i到j的不经过k的最短路呢?想到了什么?floyd! floyd的本质是个dp,dp[k][i][j]代表i到j的中间节点(不包括i和j)都在区间[1,k]时,i到j的最短路。floyd算法的最外层循环是个从小到大枚举k的过程,当最外层刚刚进入第k次循环的时候 ...

    Tagged as : Poj 图论 最短路
  3. POJ 3259

    题意:一个图,有两种边,一种是双向边,权值为正,一种是单向边,权值为负。
    问能否在图中找到一个负环。

    分析:典型的找负环的题,但是这个题没有规定起点,所以直接从点1开始做bf是错误的。
    bellman-ford算法可以判断一个从源点可达的环,那这个题需要做n次bf吗?
    其实可以建立一个源,从源向每个图中的点引一条任意权值的边(不必为0),然后用bf就行了。
    本质上就是初始化和经典的初始化不同,细节见代码。

    /*
        POJ 3259
        code by heifrank
    */
    #include <cstdio>
    #include <vector>
    #include <cstring>
    #include <queue>
    #include <algorithm>
    using namespace std;
    
    const int MV = 505;
    
    vector< pair<int, int> > G[MV];
    int d ...
    Tagged as : 图论 最短路 Poj

Pages

Categories

Tags

Page 1 / 1