不忘初心
时刻前行

  1. 单源最短路问题(dij, bellman-ford && SPFA)
  2. 多源最短路问题(Floyd)
  3. 负环
  4. 最小生成树(kruskal, Prim, Boruvka)
  5. 无向图与连通性
  6. 有向图与连通性
  7. 二分图匹配(gugu)

最短路问题

给出一张图,求 1 节点到其他任意节点的最短路径,且边权为非负的

Dijkstra

贪心的求解

算法原理

每次选择 dis 最小的作为起点更新其他点的 dis

算法实现

朴素算法

花费 O(n) 的时间去寻找 dis 最小的点

堆优化

利用堆进行优化

void dij() {
    priority_queue<pii, vector<pii>, greater<pii> > f;
    for (int i = 1; i <= n; ++i) dis[i] = 0x7fffffff;
    dis[s] = 0, f.push(make_pair(0, s));
    while (!f.empty()) {
        int now = f.top().second; f.pop();
        if (vis[now]) continue;
        vis[now] = true;
        for (int i = head[now]; i; i = e[i].nxt) { int v = e[i].to;
            if (dis[v] > dis[now] + e[i].w) dis[v] = dis[now] + e[i].w, f.push(make_pair(dis[v], v));
        }
    }
}

Bellman-ford

边权为负

松弛操作

算法思想

对于每一条边都松弛 n - 1

即不断地利用三角形不等式进行更新

算法实现

朴素算法

按思想直接模拟即可

for (i = 1; i <= n; i++) dist[i] = edge_len(S, i);
for (i = 1; i < n; i++) {
    for each edge(u, v) {
        dist[v] = min(dist[v], dist[u] + edge_len(u, v));
    }
}

队列优化

事实上我们可以发现,在每一轮的松弛中,引起松弛操作的起点 u 一定在上一轮中被松弛

所以我们可以根据这一点利用队列进行优化,去除了许多不必要的松弛

void spfa() {
    queue<int> q;
    for (int i = 1; i <= n; ++i) dis[i] = 0x7fffffff;
    dis[s] = 0, q.push(s), in_queue[s] = true;
    while (!q.empty()) {
        int now = q.front(); in_queue[now] = false, q.pop();
        for (int i = head[now]; i; i = e[i].nxt) { int v = e[i].to;
            if (dis[v] > dis[now] + e[i].w) {
                dis[v] = dis[now] + e[i].w;
                if (!in_queue[v]) q.push(v), in_queue[v] = true;
            }
        }
    }
}

多源最短路问题

给定一张图,求任意两个点之间的距离

Floyd 算法

DP

算法思想

f(i, j, k) 表示从 ij,中间只能经过编号不超过 k 的点的最短路,特别的 f(i, i, k) = 1,不连通则为正无穷

算法实现

朴素算法

for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                f[i][j][k] = min(f[i][j][k - 1], f[i][k][k - 1] + f[j][k][k - 1]);
            }
        }
    }

优化

发现最后一位可以直接优化掉,那么最终

for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                f[i][j] = min(f[i][j], f[i][k] + f[j][k]);
            }
        }
    }

负环

给定一张图,判定图上是否有负环,即换上点权和为负

Bellman-Ford

算法思想

考虑 Bellman-Ford 更新的本质,即三角不等式

当出现负环时,一个节点一定会被更新无限次

而不出现负环时,一个节点最多被更新 n - 1

算法实现

Bellman-Ford

直接更新 n - 1 次,再判断是否仍右边满足三角形不等式

时间复杂度 O(nm)

bool BellmanFord() {
    memset(dis, 0x3c, sizeof dis);
    for (int t = 1; t < n; ++t) {
        bool flg = false;
        for (int i = 1; i <= cnt; ++i) { int u = e[i].fr, v = e[i].to, w = e[i].w;
            if (dis[v] > dis[u] + w) dis[v] = dis[u] + w, flg = true;
        }
        if (flg == false) break;
    }
    for (int i = 1; i <= cnt; ++i) { int u = e[i].fr, v = e[i].to, w = e[i].w;
        if (dis[v] > dis[u] + w) return true;
    }
    return false;
}

队列优化

与最短路类似,我们使用队列来优化

均摊下来,期望复杂度 O(kn)k 是每个点平均入队次数

void spfa() {
    queue<int> q;
    for (int i = 1; i <= n; ++i) dis[i] = 0x3f, in_queue[i] = 0, t[i] = 0;
    dis[1] = 0, q.push(1), in_queue[1] = true;
    while (!q.empty()) {
        int now = q.front(); in_queue[now] = false, q.pop(); 
        for (int i = head[now]; i; i = e[i].nxt) { int v = e[i].to;
            if (dis[v] > dis[now] + e[i].w) {
                dis[v] = dis[now] + e[i].w;
                t[v] ++;
                if (t[v] >= n && vis[v]) { puts("YE5"); return ; }
                if (!in_queue[v]) q.push(v), in_queue[v] = true;
            }
        }
    }
    puts("N0");
}

最小生成树

给定一张无向图,求最小生成树

kruskal

贪心

算法思想

将边按边权升序排序

对于一条边,对于这条边的原点和出点,如果不连通,则将这条边选上

正确性证明:

按照贪心的思想建出来最小生成树后,如果我们把在树上的任意一条边 i 去掉,而换成另一条边使得保证树的性质后,可以发现此时边权增大,不满足最小生成树的定义

算法实现

利用并查集维护连通性

不过均摊下来是 O(m \log \alpha(n))

貌似可以卡成 O(n\alpha(m))(重边)?

sort(e + 1, e + m + 1);
for (int i = 1; i <= m && cnt < n - 1; ++i) { int u = e[i].fr, v = e[i].to;
    if (gf(u) != gf(v)) cnt ++, fa[gf(u)] = gf(v), ans += e[i].w;
}

Prim

类似 Dijkstra

算法思想

任选一个点作为起点,在所有与起点相连的点中选择边权最小的点,并将这条边加入生成树,将这个点作为起点,重复 n - 1

正确性:任意一个点与其最近点的连边一定属于 MST

算法实现

利用优先队列维护边权最小即可

时间复杂度 O((n + m) \log n)

void prim() {
    priority_queue<pii, vector<pii>, greater<pii> > f;
    for (int i = 1; i <= n; ++i) dis[i] = 0x3c;
    dis[1] = 0, f.push(make_pair(0, 1));
    int tot = 0;
    while (!f.empty() && tot < n) {
        int u = f.top().second, rec = f.top().first; f.pop();
        if (vis[u]) continue;
        ++tot, ans += rec, vis[u] = true;
        for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].to;
            if (e[i].w < dis[v]) {
                dis[v] = e[i].w, f.push(make_pair(dis[v], v));
            }
        }
    }
}

Boruvka

多源化的 MST 算法

算法思想

考虑对于每一个连通块扩展,记录扩展连通块最少的花费 best 数组

算法实现

并查集

时间复杂度 O(m \log \alpha(n))

void boruvka() {
    bool flg = true;
    while (flg) { // 直到没有扩展发生
        flg = false;
        memset(best, 0, sizeof best);
        for (int i = 1; i <= m; ++i) {
            if (gf(e[i].fr) != gf(e[i].to) && !used[i]) {
                int fa = gf(e[i].fr), fb = gf(e[i].to);
                if (e[i].w < e[best[fa]].w) best[fa] = i;
                if (e[i].w < e[best[fb]].w) best[fb] = i;
            }
        }
        for (int i = 1; i <= n; ++i) {
            if (best[i] != 0 && !used[best[i]]) {
                flg = true; cnt ++, ans += e[best[i]].w;
                used[best[i]] = true, merge(e[best[i]].fr, e[best[i]].to);
            }
        }
    }
}

无向图与连通性

给定一张无向图,求图中的割点与桥

割点被定义为:当该点被删去后,图会分裂成多个不互相连通的子图,桥被定义为:当该边被删去后,图会分裂成多个不互相连通的组图

Tarjan

DFS 搜索树

算法思想

记录每个点的 DFS 序与 low 值,其中 low(i) 表示 i 的搜索子树中与子树中的任意节点所能到达的点中最小的 DFS 序的值

如果一个点为割点,那么其充分必要条件是该点不在环上,即没有点能够与其搜索树上的祖先相连

u 是割点 \Leftrightarrow \exist v \in \text{subtree}(u),\ low(v) \geq dfs(u)

(u, v) 是桥 \Leftrightarrow low(v) > dfs(u)

算法实现

按定义更新即可

时间复杂度 O(n)

求割点

void tarjan(int u, int fa) {
    dfn[u] = low[u] = ++dfsclock; int child_cnt = 0; bool flg = false;
    for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].to;
        if (v == fa) continue;
        if (!dfn[v]) {
            tarjan(v, u);
            child_cnt ++;
            low[u] = min(low[u], low[v]);
            if (low[v] >= dfn[u]) is_cut[u] = true, cutcnt += flg ^ 1, flg = true;;
        } else low[u] = min(low[u], dfn[v]);
    }
    if (fa == 0 && child_cnt == 1) is_cut[u] = false, cutcnt --;
}

求桥

void tarjan(int u, int fa) {
    dfn[u] = low[u] = ++dfsclock; int child_cnt = 0; bool flg = false;
    for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].to;
        if (v == fa) continue;
        if (!dfn[v]) {
            tarjan(v, u);
            child_cnt ++;
            low[u] = min(low[u], low[v]);
            if (low[v] > dfn[u]) is_bridge[i] = true, cutcnt += flg ^ 1, flg = true;;
        } else low[u] = min(low[u], dfn[v]);
    }
}

有向图与连通性

给定一张有向图,求图中的强连通分量

强连通分量被定义为,在分量中,任意两点 x, y,即存在一条路径 x \rightarrow y,也存在一条路径 y \rightarrow x

Tarjan

算法思想

由搜索树出发,我们考虑定义几种边的类型

  1. 树边,即在搜索树中的边
  2. 前向边,即在搜索树上,出端更深的边
  3. 后向边,即在搜索树上,出端更浅的边

我们发现,只要我们找到了一条前向边,那么就意味着我们找到了一条环

算法实现

按照定义即可

时间复杂度 O(n)

void tarjan(int u) {
    dfn[u] = low[u] = ++dfsclock, s.push(u), in_stack[u] = true;
    for (auto v : e[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[v], low[u]);
        } else if (in_stack[v]) low[u] = min(low[u], dfn[v]);
    }
    if (low[u] == dfn[u]) {
        int now; ++ scccnt;
        do {
            now = s.top(); s.pop();
            scc[scccnt].push_back(now), bel[now] = scccnt, in_stack[now] = false, sum[scccnt] += val[now];
        } while (now != u);
    }
}

附上缩点代码

for (int u = 1; u <= n; ++u) {
        for (auto v : e[u]) {
            if (bel[u] == bel[v]) continue;
            t[bel[u]].push_back(bel[v]);
        }
    }

OI-图论-最短路 OI-图论-最小生成树 OI-图论-负环 OI-图论-Floyd OI-图论-连通块

树链剖分知识总结
上一篇 «
正睿普转题 Day3 赛后题解与总结
» 下一篇
© 2019 - 2019 bwt's blog.
...... visits · ...... visitors