一、求最近公共祖先结点（LCA）

1. 定义

LCA（Lowest Common Ancestors），即最近公共祖先，是指在有根树中找出某两个结点u和v最近的公共祖先结点。

2. 解析

这里只说一种我个人比较喜欢的在线算法：欧拉序 + RMQ

  • 时间复杂度：预处理 O(n+nlgn)，查询只需要O(1)

  • 原理：
    欧拉序 就是在dfs遍历一棵树时经过的结点序列（包括回溯时经过的结点），显然两个结点u、v的最近公共祖先就是 欧拉序中 区间[u, v] 中深度最小的结点。（其中u、v指的是u、v在欧拉序中的第一次出现，即递归过程中的记录）
    因此我们只需要通过一遍dfs得到欧拉序euler[2 * maxn]、对应的结点深度dep[2 * maxn]，以及每个结点在欧拉序中的位置 pos[maxn]，就可以通过RMQ在O(1)实现内找到欧拉序中 区间[pos[u], pos[v]] 中深度最小的结点位置。

  • 需要维护的结构：

    • euler[2 * maxn]：欧拉序
    • dep[2 * maxn]：欧拉序中结点对应的深度
    • pos[maxn]：每个结点在欧拉序中第一次出现的位置（对应于进入递归的时候）
    • cnt：欧拉序长度
    • dp[2 * maxn][log_2maxn = 25]：对欧拉序根据dep进行RMQ预处理，dp[i][j]表示区间[i，i+2^j)中深度最小的 结点下标

  • 为了防止混乱，规定RMQ存储、询问的是区间中深度最浅的 结点下标值，并且也是通过 结点下标区间 进行询问。之后只需要利用euler数组即可映射到对应的点。另外，区间表示为 左闭右开。

3. 模板

int n, m, s;
vector<int> G[maxn];
int cnt, euler[2 * maxn], dep[2 * maxn], pos[maxn];
int dp[2 * maxn][log_2maxn];

void dfs(int u, int fa, int d) {
    pos[u] = cnt, euler[cnt] = u, dep[cnt] = d, cnt ++;
    for(int v : G[u]) if(v != fa) {
        dfs(v, u, d + 1);
        euler[cnt] = u, dep[cnt] = d, cnt ++;
    }
}

void init_RMQ() {
    for(int i = 0; i < cnt; i ++) dp[i][0] = i;  // 最短的区间
    for(int j = 1; (1 << j) <= cnt; j ++) {  // 注意先计算小区间，所以先从小到大遍历j
        for(int i = 0; i + (1 << j) - 1 < cnt; i ++) {
            int idx1 = dp[i][j - 1], idx2 = dp[i + (1 << (j-1))][j - 1];
            dp[i][j] = (dep[idx1] < dep[idx2] ? idx1 : idx2);  // RMQ中存放的是深度最小结点的下标值
        }
    }
}

int min_RMQ(int l, int r) {
    int k = log2(r - l);
    int idx1 = dp[l][k], idx2 = dp[r - (1 << k)][k];
    return dep[idx1] < dep[idx2] ? idx1 : idx2;
}

int main() {
    ......
    dfs(s, -1, 0);  // 求欧拉序euler、dep、pos
    init_RMQ();  // RMQ预处理
    while(m --) {
        ...... 
        if(pos[u] > pos[v]) swap(u, v);  // 询问u、v两个点的LCA，注意要保持欧拉序中u在v前面
        cout << euler[min_RMQ(pos[u], pos[v] + 1)] << endl;  // min_RMQ的输入、输出都是下标值，区间表示为左闭右开
    }
}

4. 例题

Luogu P3379：（题目链接）https://www.luogu.com.cn/problem/P3379

二、最大流问题（Dinic算法）

1. 定义

设源点为1, 终点为N。用 G[u][v] 表示点u、v之间的容量大小，求这样一个网络图 G 中的最大流量大小ans。

2. 解析

  • Dinic算法 求最大流 用邻接矩阵G存图更方便
  • 先进行bfs, 判断有无增广路的同时,标记每个点的层号
  • 然后根据层号进行dfs, 找增广路, 更新流值, 可能有多条不相交的增广路
  • 循环往复

3. 模板

bool bfs(){
    memset(dist, -1, sizeof(dist)); // 每次重新标记dist, 因为增加了反向边, 图已经不同
    dist[1] = 0;
    que.push(1);
    while(!que.empty()){
        int u = que.front();
        que.pop();
        for(int v = 1; v <= N; i ++){
            if(G[u][v] && dist[v] == -1){ 
            //    连接  && 未被标记 的点 
            dist[v] = dist[u] + 1;
            que.push(v); 
        }
    }
    if(dist[N] == -1) return 0;  // 若无法增广到终点，则表示没有增广路了
    return 1; 
} 

int find(int u, int low){ // low是源点到现在最窄的(剩余流量最小)的边的剩余流量 
    if(u == N) return low; // dfs出口
    for(int v = 1, a; v <= N; i ++){
        if(G[u][v] && dist[v] == dist[u] + 1 && (a = find(v, min(low, G[u][v])))){
        //   连接的    &&  是上下层关系的      && 能连通到汇点  min维护low
            G[u][v] -= a;
            G[v][u] += a; // 增加反向边 起容错作用
            return a; //只要发现一条增广路, 就返回增广的流量 
        }
    } 
    return 0; 
}

int main(){
    //....
    int ans = 0;
    while(bfs()){ // 利用bfs为每个点标记dis, 若标记不到汇点, 说明已经没有增广路 
        int temp;  // 每次增广的流量
        while(temp = find(1, INF)) ans += temp; // 根据dist进行dfs找增广路, 直到找不到为止 
    }
    cout << ans << endl;
}

全原创