算法总结

· · 算法·理论

dijkstra最短路算法

算法过程(不包含初始化)

  1. 从起点 s 开始，更新相连节点距离（其实就是如果有直接距离就更新直接距离）
  2. 将起点 s 标记为 “已访问过”
  3. 在“未访问的节点”上寻找离起点最近的节点 pos（相当于 1. 的起点）
  4. 将节点 pos 标记为“已访问过”
  5. 寻找与节点 pos 相连（有路径）的、未被标记为“已访问过”的节点 j，并更新节点 j 到初始节点最近距离
  6. 重复 3. 4. 步骤
  7. 直到所有的节点都被标记为“已访问过”，跳出循环
  8. 输出距离

代码实现(链式前向星 + dijkstra)

链式前向星此代码不详解

#include <bits/stdc++.h>

using namespace std;
//我不编译所以变量名直接用简洁明了的意思了

const int N = 节点数 + 5, M = 边数 + 5, ma = INT_MAX；
//加5是为了防止数据溢出导致RE
struct Edge{
    int to, cost, next;
}；

Edge e[M * 2];
int head[N], ans[N], cnt = 1;
//  头节点集合 最短距离
bool flag[N];//是否被标记过

void add(int from, int to, int cost){
    e[cnt].to = to;
    e[cnt].cost = cost;
    e[cnt].next = head[from];
    head[from] = cnt;
    cnt ++;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //大数据输入输出优化

    freopen("xxx.in", "r", stdin);
    freopen("xxx.out", "w", stdout);
    //读入文件类型数据（比赛用）

    int n, m, s;//n 节点数 m 边数 s 初始节点
    cin >> n >> m;
    for(int i = 1; i <= m; ++ i){
        int x, y, z;
        cin >> x >> y >> z;
        add(x, y, z);
        add(y, x, z);
        //存双向边
    }

    //以下为初始化过程
    for(int i = 1; i <= n; ++ i)
        ans[i] = ma;
    //将每个节点到初始节点的距离设为无穷大，方便更新答案
    for(int i = head[s]; i; i = e[i].next)
        ans[e[i].to] = e[i].cost;
    //步骤1
    ans[s] = 0;//初始节点到初始节点的距离为0
    flag[s] = true;
    //步骤2
    while(1){
    //步骤 6
        int tmp = ma, pos = s;
        for(int i = 1; i <= n; ++ i)
            if(!flag[i] && tmp > ans[i]){
                tmp = ans[i];
                pos = i;
            }
    //步骤3
        if(pos == s) break;
    //步骤7
        flag[pos] = true;
    //步骤4
        for(int i = head[pos]; i; i = e[i].next)
            if(!flag[e[i].to] && ans[e[i].to] > ans[pos] + e[i].cost)
                ans[e[i].to] = ans[pos] + e[i].cost;
    //步骤5

    }

    for(int i = 1; i <= n; ++ i)
        cout<< ans[i] << " ";
    //步骤8

    return 0;
}

并查集（路径压缩）

算法思想

总结四个字：路径压缩
其实就是把每个点的终点直接连接到最老的祖宗上（起点），避免了深搜的高时间复杂度，好用！！！

代码实现（并查集）

//P3367 【模板】并查集
#include <bits/stdc++.h>

using namespace std;

const int N = 节点数；
int fa[N];

int find(int x){
    if(fa[x] != x)
        fa[x] = find(fa[x]);
    return fa[x];
}//这个是找祖宗(核心代码)

int main() {
    int n, m, x, y, z;
    cin >> n >> m ;
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
    }
    //在最一开始将每个人的祖宗设为自己

    for (int i = 1; i <= m; i++) {
        cin >> z >> x >> y ;
        int a = hfind(x), b = hfind(y);
        if (z == 1) {
            if (a != b) {
                fa[b] = a;
                //注意一定是改祖宗的祖宗！(有点别扭是怎么回事)(核心代码x2)
            }
        } else {
            if (fa[x] == fa[y]) {
                cout << "Y" << endl;
            } else {
                cout << "N" << endl;
            }
        }
    }

    return 0;
}

拓扑排序

算法思想

拓扑排序是在有向无环图里实现的！！！

using namespace std;

const int N = 105; vector<int> e[N];//邻接表存边 int ind[N], outd[N];//存入度和出度 stack<int> a;//栈实现思想 vector<int> ans;//存拓扑排序的顺序

int main() { ans.push_back(1);//方便从1输出 int n; cin >> n; for (int i = 1; i <= n; ++ i) { int x; cin >> x; while (x) { e[i].push_back(x); ind[x] ++; outd[i] ++;//入度出度初始化 cin >> x; } } for (int i = 1; i <= n; ++ i) if (!ind[i]) a.push(i);//步骤2 while (!a.empty()) {//步骤3 int u = a.top();//取出栈顶 a.pop();//弹出栈顶 ans.push_back(u); for (int i = 0; i < (int)e[u].size(); ++ i) { int v = e[u][i];//指向的点 ind[v]--; if (ind[v] == 0) a.push(v); } }

for (int i = 1; i < (int)ans.size(); ++ i)
    cout << ans[i] << " ";//完美输出~

return 0;//功德圆满

}


# 动态规划（dp
- 奉上抄来的步骤
1. 定义子问题：将原问题划分为若干子问题，这些子问题应具有最优子结构的特性，即原问题的最优解可以通过子问题的最优解推导出来。
2. 构建状态转移方程：通过观察子问题之间的关系，定义状态和状态之间的转移方式。这个方程描述了问题的最优解如何由子问题的最优解计算得出。
3. 确定边界条件：确定最简单的子问题的解，也就是边界条件。这些边界条件将作为递归或迭代的终止条件。
4. 解决子问题：按照定义的状态转移方程，从最简单的子问题开始逐步解决更复杂的子问题，直到解决原问题。
5. 记忆化或建表：为了避免重复计算，可以使用记忆化技术将子问题的解存储起来，或者使用表格/数组记录子问题的解。
6. 求解原问题：通过解决子问题，得到原问题的最优解。
# 最小生成树算法
> 首先双手奉上[这个比较易懂的讲解](https://www.bilibili.com/video/BV1wG411z79G?vd_source=8b6498594bdc0b225db7065c99c525c1)
> ## Prim算法（加点）
> - 适合稠密图（视频里说的嘿嘿）