专栏文章

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

jjcs_pp
P8794题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minpx4h2
此快照首次捕获于
2025/12/02 06:25
3 个月前
此快照最后确认于
2025/12/02 06:25
3 个月前
查看原文
题意题目中已经解释的很清楚了，这里不再赘述了。
此题要求求出每两个城市的 最短路 所以考虑 弗洛伊德算法。
但是弗洛伊德算法时间复杂度为 N3N^3，直接枚举复杂度大致为 DN3DN^3，妥妥炸了。
那咋办？
这道题有一个非常重要的性质：随着天数增加，PP 指标一定单调递减，所以说这道题 具有单调性，考虑二分。
再看看，时间复杂度降到了 log⁡DN3\log DN^3。这下没问题了。
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...