本文主要是介绍Floyd+二分，蓝桥杯国赛2022[环境治理]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一、题目
1、题目描述
2、输入输出
2.1输入
2.2输出
3、原题链接
0环境治理 - 蓝桥云课 (lanqiao.cn)
二、解题报告
1、思路分析
考虑我们治理时间越长，灰尘度和越低，具有单调性
考虑 二分治理天数mid，1~n可以降低与其相连边 mid / n 点的边权
1 ~ mid % n 可以额外降低与其相连边 1点 的边权
注意边权不能低于临界值
每次更新边权跑一遍floyd
二分最小答案即可
2、复杂度
时间复杂度： O(n ^ 3 * logk)空间复杂度：O(n ^ 3)
3、代码详解
#include <bits/stdc++.h>
using i64 = long long;
const int N = 105;
int f[N][N], g[N][N], w[N][N];
int n, Q;
bool check(int x) {// 1 ~ n 增加 x / n, 1 ~ x % n 额外增加1 // 考虑O(n^2) 改边// O(n^3) 求最短路// 注意边权下限int a = x / n, b = x % n;memcpy(f, g, sizeof g);for(int i = 1; i <= n; i ++)for(int j = 1; j <= n; j ++)f[i][j] = f[j][i] = std::max(f[i][j] - a, w[i][j]);for(int i = 1; i <= b; i ++)for(int j = 1; j <= n; j ++)f[i][j] = f[j][i] = std::max(f[i][j] - 1, w[i][j]);for(int k = 1; k <= n; k ++)for(int i = 1; i <= n; i ++) for(int j = 1; j <= n; j ++) f[i][j] = std::min(f[i][j], f[i][k] + f[k][j]);i64 s = 0;for(int i = 1; i <= n; i ++) for(int j = 1; j <= n; j ++) s += f[i][j];return s <= Q;
}int main() {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);std::cin >> n >> Q;for(int i = 1; i <= n; i ++) for(int j = 1; j <= n; j ++) std::cin >> g[i][j];int l = 0, r = 0;for(int i = 1; i <= n; i ++) for(int j = 1; j <= n; j ++) std::cin >> w[i][j], r = std::max(g[i][j] - w[i][j], r);r *= n;int ans = -1;while (l <= r) {int mid = l + r >> 1;check(mid) ? r = (ans = mid) - 1 : l = mid + 1;}std::cout << ans;return 0;
}这篇关于Floyd+二分，蓝桥杯国赛2022[环境治理]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
