Floyd

_yang_yi_bo_ · 2024-08-16 12:26:27 · 算法·理论

P5663 [CSP-J2019] 加工零件

考虑存储从 1 到每个点的最短距离。

我们在考虑一些特殊的情况

当③要生产五阶零件时，①可以生产原材料，路径为① \to ② \to ① \to ② \to ③，也就是说，当到达的最短路径小于需要的零件阶数时，可以来回跑动来缩短阶数。

所以，当最短路径小于等于阶数时，且两者奇偶性相同时，是能到达的。

当③要生产三阶零件时，①可以生产原材料，路径为③ \to ④ \to ⑤ \to ①，但是最短路径为二，且最短路径与阶数的奇偶性不同。

也就是说，我们要分别存储路径为奇数的最短路径与路径为偶数的最短路径。

#include<bits/stdc++.h>
using namespace std;
int n,m,q;
vector<int> g[100005];
int dis1[100005];
int dis2[100005];
void bfs(){
    queue<int> q;
    q.push(1);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=0;i<g[u].size();i++){
            int pos=g[u][i];
            if(dis1[u]+1<dis2[pos]){
                dis2[pos]=dis1[u]+1;
                q.push(pos);
            }if(dis2[u]+1<dis1[pos]){
                dis1[pos]=dis2[u]+1;
                q.push(pos);
            }
        }
    }
}
int main(){
    cin>>n>>m>>q;
    for(int i=1;i<=m;i++){
        int u,v;
        g[u].push_back(v);
        g[v].push_back(u);
    }memset(dis1,0x3f,sizeof dis1);
    memset(dis2,0x3f,sizeof dis2);
    dis2[1]=0;
    bfs();
    while(q--){
        int l,x;
        cin>>x>>l;
        if((l%2==0&&l>=dis2[x])||(l%2==1&&l>=dis1[x])){
            cout<<"Yes\n";
        }else{
            cout<<"No\n";
        }
    }
    return 0;
} 

B3647 【模板】Floyd

Floyd 板子题。

首先，我们先存储两点之间的直接最短路径，若两点无法联通，存储为极大值。

接着枚举中转点，dis_{i_j} 保存之前添加中转点之后的最短路径。

所以添加完成 n 次后，相当于得到了所有点作为中转点的答案。

#include<bits/stdc++.h>
using namespace std;
int n,m;
int dis[105][105];
void floyd(){
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(dis[i][j]>dis[i][k]+dis[k][j]){
                    dis[i][j]=dis[i][k]+dis[k][j];
                }
            }
        }
    }
}
int main(){
    cin>>n>>m;
    memset(dis,0x3f,sizeof dis);
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        dis[u][v]=min(dis[u][v],w);
        dis[v][u]=min(dis[v][u],w);
    }for(int i=1;i<=n;i++){
        dis[i][i]=0;
    }floyd();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cout<<dis[i][j]<<" ";
        }cout<<"\n";
    }
    return 0;
} 

P1828 [USACO3.2] 香甜的黄油 Sweet Butter

这道题的题意可以转化为：求出每一个点与另一个点之间的最短路，枚举一个点，求输入的每一个点与这个点的路径之和，取最小值就行了。

要注意此题要开 long long ，初始值不能用 memset(dis,0,sizeof dis)，因为 memset 是按字节存储，初始的极大值大概在 4 \times 10^{18}，求和时有可能爆 long long。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,q,mini=1e18;
int a[1005];
int dis[1005][1005];
void floyd(){
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(dis[i][j]>dis[i][k]+dis[k][j]){
                    dis[i][j]=dis[i][k]+dis[k][j];
                }
            }
        }
    }
}
signed main(){
    cin>>q>>n>>m;
    for(int i=1;i<=q;i++){
        cin>>a[i];
    }for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            dis[i][j]=1e18;
        }
    }
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        dis[u][v]=min(dis[u][v],w);
        dis[v][u]=min(dis[v][u],w);
    }for(int i=1;i<=n;i++){
        dis[i][i]=0;
    }floyd();
    for(int i=1;i<=n;i++){
        int cnt=0;
        for(int j=1;j<=q;j++){
            cnt+=dis[a[j]][i];
        }mini=min(mini,cnt);
    }cout<<mini;
    return 0;
} 

P1364 医院设置

此题可以看成是在二叉树上进行 Floyd。

其实是一样的，我们在输入左子树与右子树时，若不为空，则在当前点与 i 建一条边权为 1 的无向边。

和P1828 [USACO3.2] 香甜的黄油 Sweet Butter一样，枚举医院的点，计算距离和，取最小值就行了。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,q,mini=1e18;
int a[105];
int dis[105][105];
int w[105];
void floyd(){
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(dis[i][j]>dis[i][k]+dis[k][j]){
                    dis[i][j]=dis[i][k]+dis[k][j];
                }
            }
        }
    }
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            dis[i][j]=1e18;
        }
    }
    for(int i=1;i<=n;i++){
        int u,v;
        cin>>w[i]>>u>>v;
        if(u!=0){
            dis[u][i]=1;
            dis[i][u]=1;
        }if(v!=0){
            dis[v][i]=1;
            dis[i][v]=1;
        }   
    }for(int i=1;i<=n;i++){
        dis[i][i]=0;
    }floyd();
    for(int i=1;i<=n;i++){
        int cnt=0;
        for(int j=1;j<=n;j++){
            cnt+=dis[i][j]*w[j];
        }mini=min(mini,cnt);
    }cout<<mini;
    return 0;
} 

完结撒花~