Floyd进阶①

_yang_yi_bo_ · 2024-09-25 13:28:51 · 个人记录

P2888 [USACO07NOV] Cow Hurdles S

我们枚举一个中转点 k，i \to k \to j 需要跨越的栏的最大值就是 i \to k 的栏杆与 k \to j 的栏的最大值，若这个最大值小于当前 i \to j 最小的栏，就将 i \to j 最小的栏替换为这个最大值。

经过三重循环，即可得出各个点之间经过的栏中的最大值的最小值。

#include<bits/stdc++.h>
using namespace std;
int n,m,t;
int dis[305][305];
void floyd(){
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                dis[i][j]=min(dis[i][j],max(dis[i][k],dis[k][j]));
            }
        }
    }
}
int main(){
    cin>>n>>m>>t;
    memset(dis,0x3f,sizeof dis);
    for(int i=1;i<=m;i++){
        int x,y,w;
        cin>>x>>y>>w;
        dis[x][y]=w;
    }floyd();
    while(t--){
        int x,y;
        cin>>x>>y;
        if(dis[x][y]>1e9){
            cout<<-1;
        }else{
            cout<<dis[x][y];
        }cout<<"\n";
    }
    return 0;
} 

P2912 [USACO08OCT] Pasture Walking G

此题看上去是一个普通的 Floyd，但是要加上一个优化。

在 i \to k 不连通的时候，直接不计算下面的内容了。

由于这是一棵树，树上只有 n-1 条边，边数非常小，加上这个优化能排除掉很多多余的中转点，所以才能AC。

#include<bits/stdc++.h>
using namespace std;
int n,m,t;
int dis[3005][3005];
void floyd(){
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            if(dis[i][k]>1e9){
                continue;
            }for(int j=1;j<=n;j++){
                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
            }
        }
    }
}
int main(){
    cin>>n>>t;
    memset(dis,0x3f,sizeof dis);
    for(int i=1;i<n;i++){
        int x,y,w;
        cin>>x>>y>>w;
        dis[x][y]=dis[y][x]=w;
    }floyd();
    while(t--){
        int x,y;
        cin>>x>>y;
        if(dis[x][y]>1e9){
            cout<<-1;
        }else{
            cout<<dis[x][y];
        }cout<<"\n";
    }
    return 0;
} 

P1841 [JSOI2007] 重要的城市

每一条路成为更短的路径，都是因为加入了中转点。

若加入一个中转点是使最短路更小，则覆盖当前的关键的点，存储这个中转点为关键的点。

若加入一个中转点 = 当前的最短路，则将关键的点清零。

计算存储了多少关键的点即可。

#include<bits/stdc++.h>
using namespace std;
int n,m;
bool f=1;
bool ans[3005];
int dis[3005][3005];
int vis[3005][3005];
set<int> st;
void floyd(){
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            if(i==k){
                continue;
            }for(int j=1;j<=n;j++){
                if(j==k||i==j){
                    continue;
                }if(dis[i][k]+dis[k][j]<dis[i][j]){
                    dis[i][j]=dis[i][k]+dis[k][j];
                    vis[i][j]=k;
                }else if(dis[i][k]+dis[k][j]==dis[i][j]){
                    vis[i][j]=0;
                }
            }
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            dis[i][j]=1e9;
        }
    }for(int i=1;i<=m;i++){
        int x,y,w;
        cin>>x>>y>>w;
        dis[x][y]=dis[y][x]=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++){
            ans[vis[i][j]]=1;
            if(vis[i][j]){
                f=0;
            }
        }
    }if(f){
        cout<<"No important cities.";
    }else{
        for(int i=1;i<=n;i++){
            if(ans[i]){
                cout<<i<<" ";
            }
        }
    }
    return 0;
}