floyd 进阶

xuanxiao2024 · 2024-09-25 12:55:09 · 个人记录

本课知识

主要学 floyd

floyd 求树的深度

1. 直接跑 DFS ，得到递推式 dep[i] = dep[fa] + 1;
2. floyd，dis[root(根节点)][i] 其实就是 dep[i]

floyd 求树的宽度

1. BFS，找到入队节点个数最多的一层 (不好写)
2. DFS，拿一个桶 T，用来装 dep[i](dep[i]相同的就是同一层的)，找到最多的那个。
3. floyd，与 DFS 一样，上文已经说过 dis[root(根节点)][i] 其实就是 dep[i]

floyd 在树上问题很好用，但是容易被卡空间时间(时间 O(n^3) ，空间 O(n^2) )

1. 可以求深度
2. 可以求宽度
3. 可以求任意两点的距离

如用别的算法，代码较长(如 LCA )

P3884 [JLOI2009] 二叉树问题

数据范围 n 最多才 100 ， floyd 轻松过

Code

LCA

自己额外写的

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
typedef long long ll;
const ll MX = 7;
ll n,root,dep_mx,t[105],mx,dep[105],dp[105][10];
bool vis[500005];
vector<ll> G[500005];

void dfs(ll x,ll f){
    dep[x] = dep[f] + 1;
    dp[x][0] = f;
    for(int i = 1;(1 << i) <= dep[x];i++){
        dp[x][i] = dp[dp[x][i - 1]][i - 1]; 
    }
    for(int i = 0;i < G[x].size();i++){
        ll nx = G[x][i];
        if(nx != f){
            dfs(nx,x);
        }
    }
    return ;
}

ll LCA(ll x,ll y){
    bool f = 0;
    ll lx = 0,ly = 0;
    if(dep[x] < dep[y]) swap(x,y),f = 1;
    for(int i = MX;i >= 0;i--){
        if(dep[x] - (1 << i) >= dep[y]){
            x = dp[x][i];
            lx += (1 << i);
        }
    }
    if(x == y){
        if(f) return lx + 2 * ly;
        else return 2 * lx + ly;
        return 0;
    }
    for(int i = MX;i >= 0;i--){
        if(dp[x][i] != dp[y][i]){
            x = dp[x][i];
            y = dp[y][i];
            lx += (1 << i);
            ly += (1 << i);
        }
    }
    lx++;
    ly++;
    if(f) return lx + 2 * ly;
    else return 2 * lx + ly;
    return 0;
} 

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for(int i = 1;i < n;i++){
        ll s,e;
        cin >> s >> e;
        G[s].push_back(e);
        G[e].push_back(s);
        vis[e] = 1;
    }
    for(int i = 1;i <= n;i++){
        if(vis[i] == 0){
            root = i;
        }
    }
    dfs(root,0);
    for(int i = 1;i <= n;i++){
        dep_mx = max(dep_mx,dep[i]);
        t[dep[i]]++;
        mx = max(mx,t[dep[i]]);
    }
    cout << dep_mx << '\n' << mx << "\n";
    ll x,y;
    cin >> x >> y;
    cout << LCA(x,y);
    return 0;
} 

floyd

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
typedef long long ll;
ll n,dep[105],root,dis[105][105],t[105],dep_mx,mx;

void init(){
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= n;j++){
            dis[i][j] = 1e14;
            if(i == j){
                dis[i][j] = 0;
            }
        }
    }
}

void floyd(){
    for(int x = 1;x <= n;x++){
        for(int s = 1;s <= n;s++){
            for(int e = 1;e <= n;e++){
                dis[s][e] = min(dis[s][e],dis[s][x] + dis[x][e]);
            }
        }
    }
    return ;
}

int main(){
    cin >> n;
    init();
    for(int i = 1;i < n;i++){
        ll s,e;
        cin >> s >> e;
        dis[s][e] = 1;
        dis[e][s] = 2;
    }
    floyd();
    for(int i = 1;i <= n;i++){
        dep[i] = dis[1][i];
        dep_mx = max(dep_mx,dep[i]);
        t[dep[i]]++;
        mx = max(mx,t[dep[i]]);
    }
    cout << dep_mx + 1 << "\n" << mx << "\n";
    ll s,e;
    cin >> s >> e;
    cout << dis[s][e] << "\n";
    return 0;
} 

P2888 [USACO07NOV] Cow Hurdles S