NCC-79601 Captain's Log

NCC-79601 Captain's Log

To boldly go where no one has gone before.

【复习笔记】Week 2 图论

posted on 2019-10-27 23:04:41 | under 复习笔记 |

最常用的化解技巧是建虚点。

DAY 1

跑最短路也是可以建虚点的。

Dijsktra

Dijsktra 中也需要记录 vis[] 表示当前点的最短路是否已经确定,否则可能造成重复枚举同一个点周围的边,导致冗余的松弛尝试,使时间变慢。

只要出现负权边,Dijsktra 即不能使用。

注意:对于二重费用(在第一重费用最小的同时使第二重费用最小)的问题,用 SPFA 极易 TLE。这时可以采用重新重载小于号的方法。在普通的 Dijsktra 中,堆顶存放的是 dis 最小的点,每次取出这个点对其周围的点进行松弛;而在二重费用的题目中,则可以把这个规则进行改进,即堆顶保存 disfee 都最小的点。这样可以保证每个点从堆中取出来的时候,都取到了二重费用的最小值。

struct node {
    int u; ll dis, fee;
    bool operator < (const node &rhs) const {
        if (dis != rhs.dis)
            return dis > rhs.dis;
        return fee > rhs.fee;
        // 二重费用的重载小于号
    }
    node(int src_u, ll src_dis, ll src_fee) {
        u   = src_u;
        dis = src_dis;
        fee = src_fee;
    }
};
priority_queue<node> q;

void dijsktra() {
    memset(dis, 0x3f, sizeof(dis));
    memset(fee, 0x3f, sizeof(fee));
    dis[s] = fee[s] = 0;
    q.push(node(s, 0, 0));
    while (!q.empty()) {
        int u = q.top().u;
        q.pop();
        if (vis[u])
            continue;
        vis[u] = true;
        for (int i = head[u]; i; i = edge[i].next) {
            int v = edge[i].to; ll w = edge[i].w, c = edge[i].c;
            if (dis[u] + w < dis[v]) {
                dis[v] = dis[u] + w;
                fee[v] = fee[u] + c;
                // 更新最小费用
                q.push(node(v, dis[v], fee[v]));
            } else if (dis[u] + w == dis[v] && fee[u] + c < fee[v]) {
                fee[v] = fee[u] + c;
                q.push(node(v, dis[v], fee[v]));
                // 似乎这里不再入堆也是可以的
            }
        }
    }
    return ;
}

SPFA

记得每次从队列取出点的时候,要把 vis[u] 清为 false,否则原地爆炸。

SPFA 判负环时,dfs - SPFA 固然是个又好又快的方法,然而我觉得通用性不如下面这种方法强:记录每个点当前最短路径上的点数 cnt[u],若发现 cnt[u] > n 则说明出现负环。当然,这种做法的复杂度为 $O(mn)$,很容易就被卡掉了;不过,大部分情况下,加上快读、inlineregister 还是能够卡过。

bool SPFA() {
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    while (!q.empty())
        q.pop();
    dis[1] = 0;
    cnt[1] = 1;
    // 节点数从 1 开始
    q.push(1);
    while (!q.empty()) {
        int u = q.front();
        vis[u] = false;
        q.pop();
        for (int i = head[u]; i; i = edge[i].next) {
            int v = edge[i].to, w = edge[i].w;
            if (dis[u] + w < dis[v]) {
                dis[v] = dis[u] + w;
                cnt[v] = cnt[u] + 1;
                if (cnt[v] > n)
                    return true;
                if (!vis[v]) {
                    vis[v] = true;
                    q.push(v);
                }
            }
        }
    }
    return false;
}

差分约束

差分约束系统推出的条件,是跑完 SPFA 之后整张图所满足的。所以,等价条件 dis[u] + w <= dis[v] 该跑 最长路dis[u] + w >= dis[v] 该跑 最短路

最长路型差分约束系统的条件转换:

  1. $a-b\geq c \Leftrightarrow$ dis[b] + c <= dis[a] $\Leftrightarrow$ build_edge(b, a, c)
  2. $a-b\leq c \Leftrightarrow$ dis[a] - c <= dis[b] $\Leftrightarrow$ build_edge(a, b, -c)
  3. $a=b\Leftrightarrow$ build_edge(a, b, 0), build_edge(b, a, 0)

建完所有关系边之后,为了获取整张图是否存在负环的信息,一种方法是一个一个连通块地跑;另一种方法是新建虚点 0 并从虚点向所有点连一条长度为 $0$的有向边,最后 SPFA(0) 即可。

最短路树

等长路径字典序最小 的最短路树的生成方式:维护一个 conn[] 表示当前点是否被连入最短路树。按编号从小到大枚举节点 $u$,这样就能保证是按照字典序从小到大枚举;寻找 $u$所指向的所有结点 $v$,如果 conn[v] == false 并且这条边满足最短路树的性质,则证明当前这条边可以连入最短路树,那么直接在 edge2 上建边即可。

// https://www.luogu.org/problem/P5201
void build_tree() {
    conn[1] = true;
    for (int u = 1; u <= n; u++)
        for (int i = head1[u]; i; i = edge1[i].next) {
            int v = edge1[i].to, w = edge1[i].w;
            if (conn[v])
                continue;
            if (dis[u] + w == dis[v]) {
                conn[v] = true;
                build_edge(edge2, head2, id2, u, v, 1);
                build_edge(edge2, head2, id2, v, u, 1);
            }
        }
    return ;
}

DAY 2

缩点

缩完点建新图的时候,一定要记住 新图里点 $u$ 的编号是 scc[u],千万不要逮着原图的点建图(多次死亡)。

缩点的时候要考虑到 两点环 的可能,所以不能判断 $v$是否为父亲,而应该考虑 $v$是否在栈内。

void tarjan(int u) {
    dfn[u] = low[u] = ++cnt;
    s[++top] = u, ins[u] = true;
    for (register int i = h1[u]; i; i = e1[i].next) {
        int v = e1[i].to;
        if (!dfn[v]) {
            tarjan(v);
            low[u] = my_min(low[u], low[v]);
        } else if (ins[v])
            low[u] = my_min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u]) {
        scc_cnt++;
        int v;
        do {
            v = s[top--];
            ins[v] = false;
            scc[v] = scc_cnt;
            p2[scc_cnt] += p[v];
        } while (v != u);
    }
}

割点

割点需要特判 dfs 树的树根(也就是代码中的 fa ),具体为:若 fa 在 dfs 树中的儿子个数 $\geq2$,则 fa 也是一个割点。

而对于一般的点 $u$,只有在没有搜过 $u$的情况下才会考察 $u$是否为一个割点;不然就用 dfn[v] 更新 low[u] 即可。

void tarjan(int u, int fa) {
    dfn[u] = low[u] = ++dfscnt;
    int cnt = 0;
    for (int i = head[u]; i; i = edge[i].next) {
        int v = edge[i].to;
        if (!dfn[v]) {
            tarjan(v, fa);
            // 注意是把 fa 下传
            low[u] = min(low[u], low[v]);
            if (u != fa && low[v] >= dfn[u])
                cut[u] = true;
            // 普通的点
            if (u == fa)
                cnt++;
            // 特判 fa 的情况
        } else
            low[u] = min(low[u], dfn[v]);
        // 这里不需要再带上判割点的语句
    }
    if (u == fa && cnt > 1)
        cut[u] = true;
    return ;
}

在基环树上,断掉所有的桥,剩下的边就是环上的边。

tarjan 找桥的过程中,需要判断反向边。

void tarjan(int u, int pre) {
    dfn[u] = low[u] = ++dfscnt;
    for (int i = head[u]; i; i = edge[i].next) {
        if (i == (pre ^ 1))
            continue;
        int v = edge[i].to;
        if (!dfn[v]) {
            tarjan(v, i);
            if (low[v] > dfn[u])
                cut[i] = true;
            low[u] = min(low[u], low[v]);
        } else
            low[u] = min(low[u], dfn[v]);
    }
    return ;
}

DAY 3

欧拉回路

半欧拉回路的起点必须为奇数度数点,而欧拉图的起点可以任意取。注意:有可能需要倒序记录路径。

void hierholzer(int u) {
    for (int v = 'A'; v <= 'z'; v++)
        if (G[u][v]) {
            G[u][v] = G[v][u] = 0;
            hierholzer(v);
        }
    res[tail--] = u;
    return ;
}

最小生成树

Kruskal

Kruskal 的复杂度由边数 $m$决定,因此太稠密的图不能跑 Kruskal(然而这种情况并不多见)。

Prim

Prim 的思路类似 Dijsktra,并且主函数也只有一小点区别。也就是说,维护一个 dis[u] 表示点 $u$到当前生成树的最短距离;每次找出不在生成树中的 dis[] 最小的点,并连入生成树中。当然,由于思路和 Dijsktra 相似,Prim 也是可以加堆优化的。不加堆优化的 Prim 在超级稠密图中的性能优于 Kruskal。

// Prim 的邻接矩阵写法
void prim() {
    memset(dis, 0x3f, sizeof(dis));
    for (int i = 1; i <= n; i++)
        dis[i] = min(dis[i], G[1][i]);
    int u = 1;
    while (++tot < n) {
        vis[u] = true;
        int minn = 0x3f3f3f3f;
        for (int i = 1; i <= n; i++)
            if (!vis[i] && dis[i] < minn) {
                u = i;
                minn = dis[i];
            }
        ans += minn;
        for (int i = 1; i <= n; i++)
            if (!vis[i] && G[u][i] < dis[i])
                dis[i] = G[u][i];
    }
    return ;
}

最小生成森林

最小生成森林可以看作所有树的根都连到超级根上的最小生成树,所以从超级根向每一个可以作为树根的点连一条边,即可获得最小生成森林。这里又用到了 建虚点 的方法。当然,最小生成森林也可以简单地用并查集维护,只需要统计 fa[i] == i 的点即可。

事实上,只要涉及到 一条边减少一个联通块 的问题,极有可能与最小生成树 / 最小生成森林相关。

DAY 4

二分图染色

只要一个图中没有奇环,那么这个图就是一个二分图。通常可以使用黑白染色法把一个图转化为二分图。二分图的核心在于 如何建图

二分图的题目中,点和边的实际意义是很灵活的,比如可以把坐标系上的点 $P$当成边,从 $x_P$向 $y_P$连一条边;也可以把一个网格图黑白染色后两两连边,每条边代表将这条边所连的两个点放在同一个矩形里。

不过,因为二分图中的点只有 x[]y[] 两列,所以对于二维网格图上的点,需要先把点映射到一个数字上,然后才能放到点列当中。

二分图匹配

匈牙利算法 的本质是寻找增广路(也就是进行匹配协商)。复杂度为 $O(nm)$。由于 vis[u] 记录的是点 $u$是否在当前增广路上,所以 每次找增广路后都需要把 vis[] 清零

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 10;
int cx[MAXN], cy[MAXN], G[MAXN][MAXN];
bool vis[MAXN];
int n, m, e, ans = 0;

bool hungary(int x) {
    for (int y = 1; y <= m; y++)
        if (!vis[y] && G[x][y]) {
            vis[y] = true;
            // 标记当前点已经在增广路上
            if (!cy[y] || hungary(cy[y])) {
                // 若还能找到增广路 / 进行协商
                cx[x] = y;
                cy[y] = x;
                return true;
            }
        }
    return false;
}

int main() {
    memset(cx, 0, sizeof(cx));
    memset(cy, 0, sizeof(cy));
    // 必须初始化
    scanf("%d %d %d", &n, &m, &e);
    for (int u, v; e; e--) {
        scanf("%d %d", &u, &v);
        if (u > n || v > m)
            continue;
        G[u][v] = 1;
    }
    for (int i = 1; i <= n; i++) {
        memset(vis, 0, sizeof(vis));
        // 每次都必须 memset()
        ans += hungary(i);
    }
    // 从每个点尝试寻找增广路,若找到增广路则 ans++
    printf("%d", ans);
    return 0;
}

当然,每次对 vis[] 进行一次 memset() 比较慢。为了加速,可以把 vis[] 改成时间戳,也就是下面的写法:

bool hungary(int x) {
    for (int y = 1; y <= n; y++)
        if (G[x][y] && vis[y] != cur) {
            vis[y] = cur;
            if (!cy[y] || hungary(cy[y])) {
                cx[x] = y;
                cy[y] = x;
                return true;
            }
        }
    return false;
}

int match() {
    memset(cx, 0, sizeof(cx));
    memset(cy, 0, sizeof(cy));
    memset(vis, 0, sizeof(vis));
    cur = 1;
    int res = 0;
    for (int i = 1; i <= n; i++, cur++)
        res += hungary(i);
    return res;
}

二分图的一些性质

最小点覆盖

最小点覆盖: 选取最少的一些点使得所有边都与这些点相连。

二分图中,最小点覆盖 $=$最大匹配

例题: 有一些障碍物位于一张 $n\times n$的网格图上,每次可以消除一行或者一列上的所有障碍物,求最少需要消除多少次才能清除所有障碍物。

分析: 对于每个障碍物 $(x,y)$,从 $x$向 $y$连一条边,每条边代表一个障碍物。那么可以看出,只要选出一个点 $x$,与 $x$相连的所有边(即横坐标为 $x$的所有障碍物)都会被覆盖;而题目要求所有边都被覆盖。所以,问题就转化为了最小点覆盖。

// http://poj.org/problem?id=3041
#include <iostream>
#include <stdio.h>
#include <cstring>
using namespace std;
const int MAXN = 510;
int n, k;
int G[MAXN][MAXN], cx[MAXN], cy[MAXN];
bool vis[MAXN];

bool hungary(int x) {
    for (int y = 1; y <= n; y++)
        if (G[x][y] && !vis[y]) {
            vis[y] = true;
            if (!cy[y] || hungary(cy[y])) {
                cx[x] = y;
                cy[y] = x;
                return true;
            }
        }
    return false;
}

int match() {
    int res = 0;
    for (int i = 1; i <= n; i++) {
        memset(vis, 0, sizeof(vis));
        res += hungary(i);
    }
    return res;
}

int main() {
    memset(cx, 0, sizeof(cx));
    memset(cy, 0, sizeof(cy));
    scanf("%d %d", &n, &k);
    for (int x, y; k; k--) {
        scanf("%d %d", &x, &y);
        G[x][y] = 1;
    }
    printf("%d", match());
    return 0;
} 

最小边覆盖

最小边覆盖: 选取最少的一些边使得所有点都与这些边相连。

二分图中,最小边覆盖 $=$总点数 $-$最大匹配数

例题: 有一个网格,上面有一些可选点,每次可以覆盖一个 $1\times2$大小的矩形,求出把所有点都覆盖住的最小覆盖次数。

分析: 考虑如何建图。先把图黑白染色,对于每个黑色可选点,向上下左右的白色可选点连边。对于任意一条边,选取这条边代表这条边所连的两点在同一矩形内;而题目要求所有点都被覆盖。所以,问题就转化为了最小边覆盖。

// poj.org/problem?id=3020
#include <iostream>
#include <stdio.h>
#include <cstring>
using namespace std;
const int MAXN = 3e3 + 10;
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
int G[MAXN][MAXN];
int T, h, w, n;
char s[MAXN][MAXN];
int cx[MAXN], cy[MAXN];
bool vis[MAXN];

bool accept(int x, int y) {
    return x > 0 && x <= h && y > 0 && y <= w;
}

int getid(int x, int y) {
    return (x - 1) * w + y;
}
// 需要把点映射到一个数上,方便连边

bool hungary(int x) {
    for (int y = 1; y <= n; y++)
        if (!vis[y] && G[x][y]) {
            vis[y] = true;
            if (!cy[y] || hungary(cy[y])) {
                cx[x] = y;
                cy[y] = x;
                return true;
            }
        }
    return false;
}

int match() {
    int res = 0;
    for (int i = 1; i <= n; i++) {
        memset(vis, 0, sizeof(vis));
        res += hungary(i);
    }
    return res;
}

int init() {
    memset(G, 0, sizeof(G));
    memset(cx, 0, sizeof(cx));
    memset(cy, 0, sizeof(cy));
    int res = 0;
    for (int x = 1; x <= h; x++)
        for (int y = 1; y <= w; y++)
            if (s[x][y] == '*') {
                res++;
                if ((x + y) & 1)
                    continue;
                for (int k = 0; k < 4; k++) {
                    int nx = x + dx[k];
                    int ny = y + dy[k];
                    if (!accept(nx, ny))
                        continue;
                    if (s[nx][ny] == '*')
                        G[getid(x, y)][getid(nx, ny)] = 1;
                }
            }
    return res;
}

int main() {
    scanf("%d", &T);
    while (T-- && scanf("%d %d", &h, &w)) {
        for (int i = 1; i <= h; i++)
            scanf("%s", s[i] + 1);
        n = h * w;
        int tot = init();
        printf("%d\n", tot - match());
    }
    return 0;
}

DAY 5

树链剖分

剖完以后 $u,v$的跳转非常易错,需要判断的是 top[u]top[v] 的深度关系 而不是 uv

void Update(int u, int v, ll c) {
    c %= p;
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]])
            swap(u, v);
        // 注意是 dep[top[u]] < dep[top[v]]
        edit_tree(1, dfn[top[u]], dfn[u], c);
        u = fa[top[u]];
    }
    if (dep[u] > dep[v])
        swap(u, v);
    edit_tree(1, dfn[u], dfn[v], c);
    return ;
}

DAY 6

树上问题

一般树上问题的解决思路是考虑子树,然后考虑子树能够上传些什么给父节点。比如树上链问题,单独考虑一棵子树的话,子树内的链可以分为三种情况:

  1. 链在子树内,且不经过根节点;
  2. 链在子树内,且经过根节点;
  3. 链不全在子树内。

分别考虑每种情况对应的处理方法,就可以分治地解决一些树上问题(2018 D1T3)。

树的重心

定义:选取树上的一个点作为树根,使得最大子树最小,则这个点为树的重心。

求法:以任意点为根跑一遍 dfs,然后统计 max(size[v], n - size[u] - 1) 最小的点,即可获得重心。

一些性质

树中所有点到某节点的距离和中,到重心的距离和是最小的;若有两个重心,则其距离和相等;

把两个树通过一条边相连得到一棵新树,那么新树的重心在连接原来两个树的重心的路径上;

添加或删除一个叶子,那么树的重心最多只移动一个点。

树的直径

定义:树上任意两点的最长距离为树的直径。

直径共有两种求法,都是 $O(n)$。

贪心求法:正反两遍 dfs,第一次以任意节点为根 dfs 到最远的点 $u$,第二次从 $u$开始 dfs 到最远的点 $v$,则 $u\rightarrow v$即树的直径。

int dia = 0, p;

void dfs(int u, int fa, int pre) {
    if (pre > dia) {
        dia = pre;
        p = u;
    }
    for (int i = head[u]; i; i = edge[i].next) {
        int v = edge[i].to, w = edge[i].w;
        if (v == fa)
            continue;
        dfs(v, u, pre + w);
    }
    return ;
}

inline void prework() {
    dfs2(1, 1, 0);
    dfs2(p, p, 0);
    return ;
}

动规求法(适用于所有情况): $f[u]$表示从 $u$开始向下能够延伸的最长链长度,每次对于一个儿子 $v$,先用 $f[u]+f[v]+dis[u\rightarrow v]$更新答案,然后用 $f[v]+dis[u\rightarrow v]$更新 $f[u]$。这样可以保证不会重复计算同一条链。

一些性质

设两棵树的直径分别是 $(u_1\rightarrow v_1), (u_2\rightarrow v_2)$,则用一条边将两棵树相连,新的直径 $(u\rightarrow v)$一定满足 $u,v\in \{u_1,u_2,v_1,v_2\}$;

若给树加一个节点,新的直径最多改变一个端点。

总结

再次强调图论的经典处理方法:建反图,建虚点,边排序。

在这些知识点中,有关树的部分很可能是和树形 dp 结合考察,因此要向两个方向试探,不能局限思维。点和边的意义也不能局限于常见的套路,比如二分图中,边的意义甚至是点。涉及到树上查询的问题,一般是用树上倍增实现;如果用树链剖分 + 线段树则时间复杂度会多出一个 $logn$,这种情况下就需要用 ST 表使得单次查询复杂度达到 $O(1)$。

总而言之,图论的难点就在于建模。


$\footnotesize\text{Weathering With You}$

0249c3e1ddc8751e891a8c98d0fbec85.png bc70240efe3cb848bbc83ca2f02f54b4.png da0aecfae654a461bca35a68f7b24b83.png

重拾那份爱的勇气,纵使世界就这样疯狂下去,我毫不在意

跨越无尽黑夜,逃离阳光无法企及之地

无论是晴是雨,不管多远距离,也一定要去见你

当大地失去了重力,千年一遇的奇迹

我和你,十指相扣,翱翔天际

「呐,现在开始就要放晴了哦。」

——希望百分百晴天女孩的祈祷,也能驱散你心中的阴云。

$\large\texttt{by NCC-79601}$

$\footnotesize\text{Weathering With You}$