P8794 [蓝桥杯 2022 国 A] 环境治理

jcs_pp · 2025-10-03 11:36:18 · 题解

题意题目中已经解释的很清楚了，这里不再赘述了。

此题要求求出每两个城市的 最短路 所以考虑 弗洛伊德算法。

但是弗洛伊德算法时间复杂度为 N^3，直接枚举复杂度大致为 DN^3，妥妥炸了。

那咋办？

这道题有一个非常重要的性质：随着天数增加，P 指标一定单调递减，所以说这道题 具有单调性，考虑二分。

再看看，时间复杂度降到了 \log DN^3。这下没问题了。

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int n,q;
int d[N][N],l[N][N];
int dp[N][N];
int check(int day){
    int sum=0;
    memcpy(dp,d,sizeof d);
    for(int i=0;i<n;i++){
        int t=day/n+(day%n>i); 
        for(int j=0;j<n;j++){
            dp[i][j]-=t;
            if(dp[i][j]<l[i][j]) dp[i][j]=l[i][j];
            dp[j][i]-=t;
            if(dp[j][i]<l[j][i]) dp[j][i]=l[j][i];
        }
    }
    for(int k=0;k<n;k++)//弗洛伊德 
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            sum+=dp[i][j];
    return sum<=q;
}
int main(){
    cin>>n>>q;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>d[i][j];
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){//读入 
            cin>>l[i][j];
        }
    }
    int l=1,r=1e9+10,ans=-1;//二分 
    while(l<=r){
        int mid=l+r>>1;
        if(check(mid)){
            ans=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    cout<<ans;
    return 0;
}