图论

最短路

（1）Floyd

for(int k = 1; k <= N; k++)

    for(int i = 1; i <= N; i++)

        for(int j = 1; j <= N; j++)

            A[i][j] = A[i][k] + A[k][j];

（2）堆优化 Dijkstra

用 priority_queue 做堆，对于每次弹出的点

  标记访问

对于所有能访问到的点

  松弛

若未访问，压入堆中

（3）Spfa

用 queue 做队列，对于每次弹出的点

  消除标记

对于所有能访问的点

  松弛

若未标记，则标记，进入队列

最小生成树

（1）Kruskal

并查集初始化

边权排序

如果边上两点不在同一集合内

  合并两点

将边加入最小生成树

（2）Prim

//定义集合 A B

任选 A 中一个节点，并加入 B

删除该节点

选一个在所有连接 A 和 B 权值最小的边

将两个节点连接

边数++

将 A 中节点删除并加入到 B 中.

若边数为n-1

  完成最小生成树

否则

  继续选择

强连通分量

Tarjan

对于 Dfs 每次到的节点

  初始化 dfn[x] = low[x] = ++dfs_clock

把节点压入栈中

对于所有能访问到的节点

  如果 dfn 为 0（未Dfs到）

    Dfs 该节点

  更新 low[x] = min(low[x], low[该节点])

  若不为 0 且 不在栈中

    low[x] = min(low[x], dfn[该节点])

如果 low[x] == dfn[x]

  弹出栈中元素，直到弹出的元素等于x

  则弹出的元素属于一个强连通分量

深搜

void Dfs(/*当前状态*/){

    if(/*满足结束条件*/){

        /*记录最优解*/ 

        return;

    }

    for(int i = a; i <= b; i++){

        /*由i生成新的当前状态*/

        /*标记新状态*/

        if(/*新状态满足约束条件*/ && /*新状态可能成为答案*/){

            dfs(/*新状态*/); 

        }

        /*恢复当前状态*/

    }

    return ;

}

 最优化剪枝 可行性剪枝 记忆化搜索 改变搜索顺序 优化搜索策略

广搜

void Bfs(){

    while(!q.empty()){

        X = q.front();

        for(int i = a; i <= b; i++){

            /*由i生成新状态Y*/

            if(/*Y合法，并且第一次访问到*/){

                q.push(Y);

            } 

        }

        q.pop();

    }

    return ;

}

优化： 

判重：hash、二叉搜索树 

双向广搜 

启发式搜索 

二分 

改写成A*

动态规划

倒推

F[n] = 初值

for(k = n+1; k >= 1; k--)//阶段

  for(i; ; )//状态

    for(j; ; )//决策

      F[k] = opt{F[k+1]+A[k, x]}

print F[1]

顺推

F[1] = 初值

for(k = 2; k <= n; k++)//阶段

  for(i; ; )//状态

    for(j; ; )//决策

      F[k] = opt{F[k-1]+A[k-1, x-1]}

print F[n]

---

添加 家长论坛微信