最近在敲PAT的题目,一开始按照题号做,做到第三题发现自己最短路径算法已经忘光了(说实话以前也没写过代码)

之后开始看算法笔记,首先就想把最短路径的问题解决了。之后应该从提高篇开始看起吧。

Dj算法模板

Dj 不能很好地处理负权路径,其他的都没啥问题。看柳姐姐的PAT小本本,也没有看到贝尔曼福特或者弗洛伊德算法。暂且之后再说。
Dj 的好处也很真实,每个节点都是访问一次的。

对于Dj算法的证明我就不看了。主要还是总结模板以及题型为主。之后应该还有很多这样的文章。

// dj 模板
int dj(int s) {
// init sth.
    d[s] = 0;
    for (int i = 0; i < N; ++i) {
        int MIN = INF, v = -1;
        for (int j = 0; j < N; ++j) {
            if (!visit[j] && d[j] < MIN) {
                MIN = d[j];v = j;
            }
        }
        if (v == -1)break;
        visit[v] = true;
        for (int k = 0; k < N; ++k) {
            if (!visit[k] && road[v][k] != INF) {
                if (road[v][k] + d[v] < d[k]) {
                    d[k] = d[v] + road[v][k];
                    // PADDING STH1.
                } else if (road[v][k] + d[v] == d[k]) {
                    // PADDING STH2.
                }
            }
        }
    }
    return 0;
}

一般来说,Dj的模板是这样子的。所有变化的东西无非就是STH1STH2

常见的一些问题与处理手段。

这里介绍的就是纯Dj来解决的问题

总结PAT中的题目,可以看到最短路径问题中,需要求出的内容包括但不仅限于

  • 最短路径的个数 num[]
  • 最短路径中点的个数 pt[]
  • 打印最短路径 pre[]
  • 最短路径的点权和 w[]

之后还有另一个问题,就是所谓的第二尺度,第三尺度。也就是当有两条及以上相同边权的最短路径的时候,所需要选出的更优的最短路径。

总结PAT中的题目,可以看到最短路径问题中,第二尺度的选取的内容包括但不仅限于

  • 最大(小)点权和
  • 最大(小)平均点权和
  • 最大(小)平均边权

之后将逐一讲解上述问题,以及对应对策。

int num[Size];
int w[Size];
int pre[Size];
int pt[Size];
fill(w,w+Size,INF);
/******/
// df(int s)
w[s] = 0
// ...
if (!visit[k] && road[v][k] != INF) {
    if (road[v][k] + d[v] < d[k]) {
        d[k] = d[v] + road[v][k];
        // PADDING STH1.
        num[k] = num[v]; // num 表示相同路径数
        pre[k] = v;  // pre 表示上一个节点
        pt[k] = pt[v] +1; // pt 表示路径中总共的点数
        w[k] = w[v] + weight[k]; // w 表示 从s点到该点的点权和
    } else if (road[v][k] + d[v] == d[k]) {
        // PADDING STH2.
        num[k] += num[v]; // 注意,当检测到重复路径的时候是这样写的,很好理解
        if(SECOND_RULER){
/*
 * SECOND_RULER
 * E.G. 
 * 1. w 鉴别(点权和)
w[k] =?= w[v] + weight[k]
 * 2. 平均点权和
double avgNew = 1.0 * (w[v] + weight[k]) / (pt[v] + 1);
double avgOld = 1.0 * (w[k]) / pt[k];
 avgNew =?= avgOld
 * 3. 平均边权和 ==》 由于路径长度相同, 可以化简为边数少(多的优先)实际上是比较pt[v]+1 和 pt[k]
 pt[v]+1 =?= pt[k] 
 */
            pre[k] = v;
            pt[k] = pt[v] +1;
            w[k] = w[v] + weight[k];
        }else if(THIRD_RULER){

        }
    }
}

Dj + DFS 解决一系列复杂问题。

纯DJ能够解决的问题比较少;比如类似于PAT中的 A1018 就解决不了,这道可能是甲等中最难的题目,因为只能用这种方法做。

其实Dj的本质是解决最短路径问题,那么只要管好最短路径问题就行了。并且把对应的最短路径给放到我们的容器里。
之后用DFS来遍历这些最短路径,也是一个非常好的思路。

那么此时需要开一个vector数组来存放最短路径。话不多说,上代码。

vector<int> preVector[Size];

if (!visit[k] && road[v][k] != INF) {
    if (road[v][k] + d[v] < d[k]) {
        d[k] = d[v] + road[v][k];
        // PADDING STH1.
        preVector[k].clear(); // 如果最短路径唯一,那么就清空并加入新节点
        preVector[k].push_back(v);
    } else if (road[v][k] + d[v] == d[k]) {
        // PADDING STH2.
        preVector[k].push_back(v); // 否则直接加入新节点
    }
}

此时pre数组就可以代表着一个递归树。利用DFS遍历可以得到若干最短序列。比如说可以是这样的。
最短路径专题与小结-ShaoBaoBaoEr's Blog

于是,就可以对该树进行遍历,模板如下

vector<int> tmpPath,bestPath;
void DFS(int v){
    if(v==start){
        tmpPath.push_back(v);
        calculate();
        tmpPath.pop_back();
        return;    
    }
    tmpPath.push_back(v);
    for(int i=0;i<pre[v].size();i++){
        DFS(pre[v][i]);
    }
    tmpPath.pop_back();
}

其中的calculate函数可以做很多操作,比如刚刚提及的参数等。
由于当前tmpPath就是一条完整的路径,所以利用非常易读的代码完成当前路径的操作。

calculate函数有两个部分

  • 计算当前路径下的各种参数,比如点权和,边权和等。
  • 根据题设条件更新全局最优值,如最优点权和,最优平均点权和等。在更新完这些全局最优值后,别忘更新最优路径。

那么剩下的计算点权和,边权和等就比较简单了,如下所示

void calculate(){
    //点权和
    int tmpWeiSum=0;
    for(int i = int(tmpPath.size()-1) ;i>=0;i--){ 
    //注意一个坑点,vector.size() 的回参是 unsigned long
    //如果外面不套int的话,i会从0跳到一个很大的正数。
        tmpWeiSum+=weight[tmpPath[i]];
    }
    //边权和
    int tmpCurveSum=0;
    for(int i = int(tmpPath.size()-1) ;i>0;i--){ 
        tmpCurveSum+=net[tmpPath[i]][tmpPath[i-1]];
    }
    // RENEW 
    /*
     * 
     */
}

其他一些问题。

  • 对于字符型与数字型互转的时候,利用unordered_map转换更快,因为它的查找速度是O(1)
  • 使用vector.size() 且逆序操作的时候,要当心越界问题,用auto往往不可取。
  • 对于数组及二维数组的初始化操作,如有可能,fill函数的泛用性优于memset

一些小感慨

这两天做的题目包括了

  • A1001-A1003
  • A1018
  • A1030
  • A1072
  • A1087

算是对最短路径算法有了更加深入的理解。感觉自己动作也够慢的,之后也得加加油了。