Skip to content

Latest commit

 

History

History
605 lines (396 loc) · 11 KB

算法思想.md

File metadata and controls

605 lines (396 loc) · 11 KB
Raw

搜索与图论

DFS

算法思想

一直走，没得走了以后，回头换个方向再一直走

空间复杂度：

使用 stack

BFS

算法思想

一次走一层，层层扩展

空间复杂度：

具有最短性

使用 queue

树图的存储

const int N = 1e5 + 10;
int h[N], e[N], ne[N], idx;

void add(int a, int b) {
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

在树/图中深搜模板

bool vis[N];

void dfs(int u) {
    vis[u] = true;
    for (int i = h[u]; i != -1; i = ne[i]) {
        if (vis[e[i]]) dfs(i);
    }
}

深搜应用：求树的重心

在树/图中广搜模板

int bfs() {
    queue<int> q;
    q.push(1);
    while (q.size()) {
        int u = q.front(); q.pop();
        for (int i = h[u]; i != -1; i = ne[i]) {
            int v = e[i];
            if (!vis[v]) {
                q.push(v);
                dis[v] = dis[u] + 1;
            }
        }
    }
    return dis[n];
}

广搜应用：拓扑序列（所有的边都是从前指向后的）

最短路

单源最短路

无负权
  1. 朴素 Dijkstra
  2. 堆优化 Dijkstra
有负权
  1. Bellman-Ford：
  2. SPFA：一般：，最坏：

多源汇最短路

Floyd：

朴素 Dijkstra（稠密图）

算法流程
  1. 初始化 dis 数组，dis[1] = 0, dis[i] = +∞
  2. 从 1 到 n
  3. t <- 不在 S 中，距离最近的点
  4. S <- t
  5. 用 t 更新其他点的距离
算法模板
int dijsktra() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    
    for (int i = 0; i < n; i++) {
        int t = -1;
        for (int j = 1; j <= n; j++)
            if (!st[j] && (t == -1 || dist[t] > dist[j])) 
                t = j;
        
        st[t] = true;
        
        for (int j = 1; j <= n; j++)
            dist[j] = min(dist[j], dist[t] + g[t][j]);
    }
    
    if (dist[n] == INF) return -1;
    return dist[n];
}

堆优化（稀疏图）

算法流程
  1. 初始化 dis 数组，dis[1] = 0, dis[i] = +∞
  2. 从 1 到 n
  3. t <- 不在 S 中，距离最近的点（利用堆维护最小值）
  4. S <- t
  5. 用 t 更新其他点的距离
算法模板（手写堆）
const int N = 2e5 + 10;
int h[N], hi[N], ih[N], cnt;
int n;

const int INF = 0x3f3f3f3f;

inline int lc(int x) {
    return x << 1;
}

inline int rc(int x) {
    return (x << 1) + 1;
}

inline void h_swap(int x, int y) {
    swap(h[x], h[y]);
    swap(hi[x], hi[y]);
    swap(ih[hi[x]], ih[hi[y]]);
}

inline void up(int i) {
    while (i >> 1 && h[i] < h[i >> 1]) {
        h_swap(i, i >> 1);
        i >>= 1;
    }
}

void down(int i) {
    int t = i;
    if (lc(i) <= cnt && h[lc(i)] < h[t]) t = lc(i);
    if (rc(i) <= cnt && h[rc(i)] < h[t]) t = rc(i);
    if (i != t) {
        h_swap(i, t);
        down(t);
    }
}


int ne[N], he[N], idx;
pair<int, int> e[N];
void add(int u, int v, int w) {
    e[idx].first = v;
    e[idx].second = w;
    ne[idx] = he[u];
    he[u] = idx++;
}

void update(int i, int v) {
    h[ih[i]] = v;
    up(ih[i]);
    down(ih[i]);
}

void remove() {
    h_swap(1, cnt--);
    down(1);
}

int dist[N];

int dijkstra() {
    for (int i = 1; i <= n; i++) {
        h[++cnt] = INF;
        ih[i] = cnt;
        hi[cnt] = i;
    }
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    update(ih[1], 0);
    for (int i = 0; i < n; i++) {
        int u = hi[1];
        int t = h[1];
        // cout << u << "|" << t << endl;
        for (int i = he[u]; i != -1; i = ne[i]) {
            int v = e[i].first;
            int w = e[i].second;
            if (dist[v] > dist[u] + w) {
                update(v, dist[u] + w);
                dist[v] = dist[u] + w;
                // cout << v << " " << dist[u] + w << endl; 
            }
        }
        remove();
    }

    if (dist[n] == INF) return -1;
    return dist[n];
}
算法模板（优先队列 ）
typedef pair<int, int> PII;
int dijsktra() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});
    
    for (int i = 0; i < n; i++) {
        auto t = heap.top(); heap.pop();
        
        int ver = t.second; distance = t.first;
        if (st[ver]) continue;
        st[ver] = true;
        
        for (int i = h[ver]; i != -1; i = ne[i]) {
            int v = e[i];
            if (dist[v] > distance + w[i]) {
                dist[v] = distance + w[i];
                heap.push({dist[v], v});
            }
        }
    }
    
    if (dist[n] == INF) return -1;
    return dist[n];
}

Bellman-Ford

算法流程
  1. 迭代 n 次
  2. 对于所有边 u, v, w
    1. dist[v] = min(dist[v], dist[a] + w);（松弛）
算法作用

算法存在负环可能不存在 最短路，但可以求出，路径长度为 k 的最短路

算法模板
int bellmanford() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for (int i = 0; i < k; i++) {
        memcpy(backup, dist, sizeof dist);	// 防止串联
        for (int j = 0; j < m; j++) {
            int uu = u[j], vv = v[j], ww = w[j];
            dist[vv] = min(dist[vv], backup[uu] + ww);
        }
    }
            
    if (dist[n] > INF / 2) return -1;
    return dist[n];
}

SPFA

算法流程
  1. while queue 不为空
  2. t <- q.front()
  3. 更新 t 的所有出边 (t, b, c)
    1. queue <- b

相当于在bellmanford算法上，加了一层优化

  1. dist[v] 想更新，一定得 dist[u] 更新之后，才会更新
  2. 利用一个队列存储待更新的点，利用 st 数组，让队列里每个点只出现一次
算法模板
int spfa() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    queue<int> q;
    st[1] = true;
    q.push(1);
    
    while (q.size()) {
        int t = q.front(); q.pop();
        st[t] = false;
        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dist[j] <= dist[t] + w[i]) continue;
            dist[j] = dist[t] + w[i];
            if (st[j]) continue;
            st[j] = true;
            q.push(j);
        }
    }
    
    if (dist[n] == INF) return -1;
    return dist[n];
}

Floyd

算法思想

动态规划

dp[k, i, j] = dp[k - 1, i, j] + dp[k, i, j]

利用前 k-1 条边 ，结合第 k 条边进行松弛

算法模板
void floyd() {
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
}

最小生成树

Prim

朴素版() 稠密图

算法流程

  1. dist[i] <- +∞
  2. 迭代 n 次
  3. t <- 到集合距离最近的点
  4. 用 t 更新其他点到集合的距离
  5. S <- t

算法模板

int prim() {
    memset(dist, 0x3f, sizeof dist);
    int res = 0;
    for (int i = 0; i < n; i++) {
        int t = -1;
        for (int j = 1; j <= n; j++)
            if (!st[j] && (t == -1 || dist[j] < dist[t])) t = j;
        if (i && dist[t] == INF) return INF;
        if (i) res += dist[t];              // 防止负权自环更新 dist[t]
        for (int j = 1; j <= n; j++)
            dist[j] = min(dist[j], g[t][j]);
        st[t] = true;
    }
    return res;
}

Kruskal() 稀疏图

算法流程

  1. 对所有边按权重从小到大排序
  2. 枚举每条边 (a, b, c)
  3. 如果 a b 在一个集合，跳过
  4. 如果 a b 不在一个集合，两个集合合并（做 n - 1 次）
int find(int x) {
    return x == p[x] ? x : p[x] = find(p[x]);
}

void combine(int x, int y) {
    p[find(x)] = find(y);
}

int kruskal() {
    sort(e, e + m, [](auto a, auto b) {
        return a.c < b.c;
    });
    for (int i = 1; i <= n; i++) p[i] = i;
    int cnt = 1;
    int res = 0;
    for (int i = 0; i < m && cnt < n; i++) {
        auto ee = e[i];
        if (find(ee.a) != find(ee.b)) {
            cnt++;
            res += ee.c;
            combine(ee.a, ee.b);
        }
    }
    if (cnt == n) return res;
    return INF;
}

二分图

二分图的判别（染色法）

算法原理

一个图是二分图，当且仅当图中没有奇数环

算法模板
bool dfs(int u, int c) {
    color[u] = c;
    for (int i = h[u]; i != -1; i = ne[i]) {
        int v = e[i];
        if (!color[v]) {
            if (!dfs(v, 3 - c)) return false;
        } else if (color[v] == color[u]) {
            return false;
        }
    }
    return true;
}

最大匹配（匈牙利算法） 实际运行时间远小于

算法流程
  1. 对于每个 左半部分的点，试图匹配右半部分
  2. 如果能匹配，那就匹配，res++
  3. 如果不能匹，递归使已经匹配好的点匹配别的，再尝试匹配
    1. 成功，那就匹配，res++ 2. 失败，这个点就跳过
算法模板
#include <iostream>
#include <cstring>
using namespace std;

const int N = 500 + 10;
const int M = 1e5 + 10;

int n1, n2, m;
int h[N], e[M], ne[M], idx;
bool st[N];
int match[N];

void add(int a, int b) {
   e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

bool find(int x) {
   for (int i = h[x]; i != -1; i = ne[i]) {
       int j = e[i];
       if (!st[j]) {
           st[j] = true;
           if (match[j] == 0 || find(match[j])) {
               match[j] = x;
               return true;
           }
       }
   }
   return false;
}

int main() {
   memset(h, -1, sizeof h);
   cin >> n1 >> n2 >> m;
   
   while (m--) {
       int a, b;
       cin >> a >> b;
       add(a, b);
   }
   
   int res = 0;
   for (int i = 1; i <= n1; i++) {
       memset(st, false, sizeof st);
       if (find(i)) res++;
   }
   
   cout << res << endl;
}