【图论2】

【图论2-1】基础树上问题

LCA 最近公共祖先/并查集

P5836 [USACO19DEC]Milk Visits S

这里我参考的是最后一个暴力模拟。。因为比较好懂。。但是会有一个TLE。
https://www.luogu.com.cn/problem/solution/P1099?page=5

P3379 【模板】最近公共祖先（LCA）

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;
const int N = 5e5 + 10, M = 2 * N; //N是点数，M是边数
const int INF = 0x3f3f3f3f;

int n, m, s, a, b;
int h[N], e[M], ne[M], idx;
//h[i]是每个点对应的邻接链表 e[i]每条边所指向的点 ne[i]每条边的下一条边 idx表示第几条边
int d[N], f[N][30];   //点的深度  f[u][k]表示u的2^k辈祖先，即从u向根节点走 2^k步到达的节点
bool st[N]; //记录每个点是否已被遍历过

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

// 处理出各个点的深度 
void dfs(int u, int dep){
    d[u] = dep;
    for(int i = 0; i < 20; i++){
        f[u][i + 1] = f[f[u][i]][i];
    }
    for(int i = h[u]; i != -1; i = ne[i]){
        int j = e[i];
        if(!d[j]){
            f[j][0] = u;
            dfs(j, dep + 1);
        }
    } 
}

int LCA(int x, int y){
    if(d[x] < d[y]) swap(x, y);
    for(int i = 20; i >= 0; i--){
        if(d[f[x][i]] >= d[y]) x = f[x][i];
        if(x == y) return x;
    }
    for(int i = 20; i >= 0; i--){
        if(f[x][i] != f[y][i]) {
            x = f[x][i];
            y = f[y][i];
        }
    }
    return f[x][0];
}

int main(){
    ios::sync_with_stdio(false);
    cin >> n >> m >> s; 
    memset(h, -1, sizeof(h));
    for(int i = 1; i < n; i++){
        cin >> a >> b;
        add(a, b);
        add(b, a);
    }
    f[s][0] = s;
    dfs(s, 1);
    while(m--){
        cin >> a >> b;
        cout << LCA(a, b) << endl;
    }
    return 0;
}

P3398 仓鼠找sugar

P4281 [AHOI2008]紧急集合 / 聚会

数的重心

P1395 会议
https://www.luogu.com.cn/blog/TheBlogOfNothingness/solution-p1395

acwing 树与图的深度优先遍历解决的就是树的重心问题。
这里我结合了y总的求树的重心的模板和题解的bfs。

【图论2-2】最短路

Floyed

P1119 灾后重建
深入理解floyed中k的含义。Floyd算法就是一个利用其它点k进行中转来求最短路的步骤。
这里每次输入时间使得村庄重建完成相当于k被更新。

spfa

P3371 【模板】单源最短路径（弱化版）

Dijkstra

P4779 【模板】单源最短路径（标准版）
使用spfa会超时。


改用dijkstra