Floyd+

xuanxiao2024 · 2024-08-17 21:31:16 · 个人记录

基础知识

\text{Floyd}

今天我们学 \text{Floyd} 的另一种用法:传递性问题

传递性问题

举个非常简单的例子

现在已知 a > b , b > c ，那么 a > c
这就是传递性问题

用 \text{Floyd} ?

是可以用 \text{Floyd}
将每个关系看成边
现在就是求是否可以到达

那 \text{Floyd} 递推公式咋办？
如果能用一个中转点来到达，那么起点一定能走到中转点，且中转点也一定能走到终点。
递推公式如下:

dis[s][e] = (dis[s][e] | (dis[s][x] & dis[x][e]));

Code

    for(int x = 1;x <= n;x++){
        for(int s = 1;s <= n;s++){
            for(int e = 1;e <= n;e++){
                dis[s][e] = (dis[s][e] | (dis[s][x] & dis[x][e]));
            }
        }
    }

扩展

这里其实还能用拓扑排序 + 关键路径
但是暂时不深究

\text{bitset}

超强！！！

bool 只有 0 和 1，但是要占 1byte
1 byte = 8 bit
也就是说，bool 虽然只有 0 和 1，但是要占 8 位
每一位都能表示 0 和 1

那有没有能够节省空间的呢？
有，\text{bitset} 横空出世!

对于传递性问题，可以拿 \text{bitset} 优化常数

如果直接拿来用，反而慢一些，因为单个位比 bool 还慢
那我们考虑枚举起点和中转点:

• 如果中转点和起点有边，那么能否通过这个点到终点就是目前邻接矩阵中转点那一行，两行直接或运算
• 如果没有，别想了，下一个吧

Code

    for(int x = 1;x <= n;x++){
        for(int s = 1;s <= n;s++){
            if(dis[x][s] == 1){
                dis[s] = (dis[s] | dis[x]);
            }
        }
    }

在 n = 1000 的情况下，他比 bool 快了大约 50 倍

B3611 【模板】传递闭包 - 洛谷 | 计算机科学教育新生态

模板传递性问题

Code

#include <iostream> 
#include <cstdio> 
#include <algorithm> 
#include <cmath>
using namespace std;
typedef long long ll;
ll n,a[105][105];

void floyd(){
    for(int x = 1;x <= n;x++){
        for(int s = 1;s <= n;s++){
            for(int e = 1;e <= n;e++){
                a[s][e] |= (a[s][x] & a[x][e]);
            }
        }
    }
}

int main(){
    cin >> n;
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= n;j++){
            cin >> a[i][j];
        }
    }
    floyd();
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= n;j++){
            cout << a[i][j] << " ";
        }
        cout << "\n";
    }
    return 0;
} 

P2881 [USACO07MAR] Ranking the Cows G - 洛谷 | 计算机科学教育新生态

如果想要确定一组数的大小关系，至少需要 n * (n - 1) / 2 条边。用 \text{Floyd} 找到所有有关系的，将n * (n - 1) / 2 减去数量，即为答案
由于数据较大，所以要开 \text{bitset}

Code

#include <iostream> 
#include <cstdio> 
#include <algorithm> 
#include <cmath>
#include <bitset>
using namespace std;
typedef long long ll;
ll n,m,mx,ans[1005],cnt = 0;
bitset<1005> dis[1005]; 
void floyd(){
    for(int x = 1;x <= n;x++){
        for(int s = 1;s <= n;s++){
            if(dis[s][x] == 1){
                dis[s] = dis[s] | dis[x];
            }
        }
    }
    return ;
}

int main(){
    cin >> n >> m;
    while(m--){
        ll s,e;
        cin >> s >> e;
        dis[s][e] = 1;
    } 
    floyd();
    for(int i = 1;i <= n;i++){
        cnt += dis[i].count();
    }
    cout << n * (n - 1) / 2 - cnt;
    return 0;
} 

P1522 [USACO2.4] 牛的旅行 Cow Tours - 洛谷 | 计算机科学教育新生态

首先求出所有牧区的直径 (跑一遍 \text{Floyd} ，找最短路，找出从每个点开始，最多能走到哪，再在同一块的最短里找最长)
然后，枚举任意两个点，只要不是一个牧区(牧区可以用染色法，DFS解决)，就牵根线。

这个大牧区的直径就是: i 能走到的最长距离 + j 能走到的最长距离 + i 与 j 之间的长度 ……等等！

考虑以上这种情况，如果你按照必须走 D-B 这条路，反而不是最优的
所以判答案时还要跟它左右两个牧区的直径比一比

Code

#include <iostream> 
#include <cstdio> 
#include <algorithm> 
#include <cmath>
#define ll long long 
#define double long double 
using namespace std;
ll n,x[155],y[155],vis[155],id = 1;
double dis[155][155],big[155],siz[155],ans = 1e18;  

double dis_long(ll i,ll j){
    return sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
}

void dfs(ll x,ll color){
    vis[x] = color;
    for(int i = 1;i <= n;i++){
        if(vis[i] == 0 && dis[x][i] < 1e18){
            dfs(i,color);
        }
    }
    return ;
}

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]);
            }
        }
    }
}

int main(){
    cin >> n;
    for(int i = 1;i <= n;i++) cin >> x[i] >> y[i];
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= n;j++){
            char c;
            cin >> c;
            if(c == '1'){
                dis[i][j] = dis_long(i,j);
            }else{
                dis[i][j] = 1e18;
            }
        }
        dis[i][i] = 0;
    }
    for(int i = 1;i <= n;i++){
        if(vis[i] == 0){
            dfs(i,id);
            id++;
        }
    }
    floyd();
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= n;j++){
            if(dis[i][j] < 1e18){
                big[i] = max(big[i],dis[i][j]);
            }
        }
        siz[vis[i]] = max(siz[vis[i]],big[i]);
    }
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= n;j++){
            if(vis[i] != vis[j]){
                double mx = max(siz[vis[i]],siz[vis[j]]);
                mx = max(mx,dis_long(i,j) + big[i] + big[j]);
                ans = min(ans,mx);
            }
        }
    }
    printf("%.6Lf",ans);
    return 0;
}