算法提高课汇总

模型抽象

• $n$个哨所: $n$个顶点.

• 指挥部设在第一个哨所: 顶点1作为起点.

• 每个顶点有足够的信使, 所有信使向所有连接的顶点移动: 广播模型.

广播模型下, 从起点到任意点一定存在最短路径. 两种理解方式:

1. 考虑从起点出发经过的时间$t\rightarrow +\infty$, 那么对于任意顶点$v$, 从起点到$v$的所有路径都会
   被信使经过. 从起点第一次到达$v$的路径就是起点到$v$的最短路.

2. 用$djkstra$的思路考虑特殊的信使: 从起点出发时, $dijstra$的思路是走路径最短的顶点, 而充足的信使
   保证一定有一个信使走到$dijstra$算法选择的顶点$u$. 同理, 到达$u$后一定有一个信使到达的是此次$dijstra$
   算法选择的顶点 $\cdots$ .所以对于任意顶点, 一定有一个信使是沿着最短路到达的.

题目求经过所有顶点的时间, 也就是到达最远的顶点的时间.

代码实现

题目数据很小, 且无负权边, 可用任意算法求得从起点到其他顶点的最短路, 求最短路的最大值即可.

$Floyd O(n^3)$

#include <cstring>
#include <iostream>

using namespace std;

const int N = 110, INF = 0x3f3f3f3f;

int n, m;
int d[N][N];

int main()
{
    cin >> n >> m;
    memset(d, 0x3f, sizeof d);
    for( int i = 1; i <= n; i ++ )  d[i][i] = 0;
    for( int i = 0; i < m; i ++ )
    {
        int a, b, c;
        cin >> a >> b >> c;
        d[a][b] = d[b][a] = min( d[a][b], c ); //防止有重边
    }

    //floyd
    for( int k = 1; k <= n; k ++ )
        for( int i = 1; i <= n; i ++ )
            for( int j = 1; j <= n; j ++ )
                d[i][j] = min( d[i][j], d[i][k] + d[k][j] );

    int res = 0;
    for( int i = 1; i <= n; i ++ )  res = max( res, d[i][1] );
    if( res == INF )    res = -1; //存在无法到达的点
    cout << res << endl;

    return 0;
}

• 注意: 如果不初始化$d[i][i] = 0$可能会出现走$(v$-->$v)$自环的路径权值更大的问题.