当前位置：首页 > article >正文

【二分查找图论】P8794 [蓝桥杯 2022 国 A] 环境治理|普及

article 2026/4/3 16:11:50

本文涉及的基础知识点

本博文代码打包下载
C++二分查找
C++图论

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

题目描述

LQ 国拥有 $n$ 个城市，从 $0$ 到 $n - 1$ 编号，这 $n$ 个城市两两之间都有且仅有一条双向道路连接，这意味着任意两个城市之间都是可达的。每条道路都有一个属性 $D$ ，表示这条道路的灰尘度。当从一个城市 A 前往另一个城市 B 时，可能存在多条路线，每条路线的灰尘度定义为这条路线所经过的所有道路的灰尘度之和，LQ 国的人都很讨厌灰尘，所以他们总会优先选择灰尘度最小的路线。

LQ 国很看重居民的出行环境，他们用一个指标 $P$ 来衡量 LQ 国的出行环境， $P$ 定义为：

$P=\sum \limits_{i=0}^{n-1} \sum \limits_{j=0}^{n-1} d(i,j)$

其中 $d (i, j)$ 表示城市 $i$ 到城市 $j$ 之间灰尘度最小的路线对应的灰尘度的值。

为了改善出行环境，每个城市都要有所作为，当某个城市进行道路改善时，会将与这个城市直接相连的所有道路的灰尘度都减少 $1$ ，但每条道路都有一个灰尘度的下限值 $L$ ，当灰尘度达到道路的下限值时，无论再怎么改善，道路的灰尘度也不会再减小了。

具体的计划是这样的：

第 $1$ 天， $0$ 号城市对与其直接相连的道路环境进行改善；
第 $2$ 天， $1$ 号城市对与其直接相连的道路环境进行改善；

……

第 $n$ 天， $n - 1$ 号城市对与其直接相连的道路环境进行改善；
第 $n + 1$ 天， $0$ 号城市对与其直接相连的道路环境进行改善；
第 $n + 2$ 天， $1$ 号城市对与其直接相连的道路环境进行改善；

……

LQ 国想要使得 $P$ 指标满足 $\leq Q$ 。请问最少要经过多少天之后， $P$ 指标可以满足 $\leq Q$ 。如果在初始时就已经满足条件，则输出 $0$ ；如果永远不可能满足，则输出 $- 1$ 。

输入格式

输入的第一行包含两个整数 $n, Q$ ，用一个空格分隔，分别表示城市个数和期望达到的 $P$ 指标。

接下来 $n$ 行，每行包含 $n$ 个整数，相邻两个整数之间用一个空格分隔，其中第 $i$ 行第 $j$ 列的值 $D_{i,j} (D_{i,j}=D_{j,i},D_{i,i} = 0)$ 表示城市 $i$ 与城市 $j$ 之间直接相连的那条道路的灰尘度。

接下来 $n$ 行，每行包含 $n$ 个整数，相邻两个整数之间用一个空格分隔，其中第 $i$ 行第 $j$ 列的值 $L_{i,j} (L_{i,j} = L_{j,i}, L_{i,i} = 0)$ 表示城市 $i$ 与城市 $j$ 之间直接相连的那条道路的灰尘度的下限值。

输出格式

输出一行包含一个整数表示答案。

样例 #1

样例输入 #1

样例输出 #1

提示

【样例说明】

初始时的图如下所示，每条边上的数字表示这条道路的灰尘度：

此时每对顶点之间的灰尘度最小的路线对应的灰尘度为：

$d (0, 0) = 0, d (0, 1) = 2, d (0, 2) = 3$ ；
$d (1, 0) = 2, d (1, 1) = 0, d (1, 2) = 1$ ；
$d (2, 0) = 3, d (2, 1) = 1, d (2, 2) = 0$ 。

初始时的 $P$ 指标为 $\times 2 = 12$ ，不满足 $\leq Q = 10$ ;

第一天， $0$ 号城市进行道路改善，改善后的图示如下：

注意到边 $(0, 2)$ 的值减小了 $1$ ，但 $(0, 1)$ 并没有减小，因为 $L_{0,1} = 2$ ，所以 $(0, 1)$ 的值不可以再减小了。此时每对顶点之间的灰尘度最小的路线对应的灰尘度为：

$d (0, 0) = 0, d (0, 1) = 2, d (0, 2) = 3$ ，
$d (1, 0) = 2, d (1, 1) = 0, d (1, 2) = 1$ ，
$d (2, 0) = 3, d (2, 1) = 1, d (2, 2) = 0$ 。

此时 $P$ 仍为 $12$ 。

第二天，1 号城市进行道路改善，改善后的图示如下：

此时每对顶点之间的灰尘度最小的路线对应的灰尘度为：

$d (0, 0) = 0, d (0, 1) = 2, d (0, 2) = 2$ ，
$d (1, 0) = 2, d (1, 1) = 0, d (1, 2) = 0$ ，
$d (2, 0) = 2, d (2, 1) = 0, d (2, 2) = 0$ 。

此时的 $P$ 指标为 $\times 2 = 8 < Q$ ，此时已经满足条件。

所以答案是 $2$ 。

【评测用例规模与约定】

对于 $30\%$ 的评测用例， $\leq n \leq 10$ ， $\leq L_{i,j} \leq D_{i,j} \leq 10$ ；
对于 $60\%$ 的评测用例， $\leq n \leq 50$ ， $\leq L_{i,j} \leq D_{i,j} \leq 10^5$ ；
对于所有评测用例， $\leq n \leq 100$ ， $\leq L_{i,j} \leq D_{i,j} \leq 10^5$ ， $\leq Q \leq 2^{31} - 1$ 。

蓝桥杯 2022 国赛 A 组 F 题。

二分查找+多源最短路

Check(mid)，多源最短路计算最短路(int)，再计算其和sum(long long)。返回sum <= Q。
二分类型：寻找首端。
参数返回：[0,10⁷]
如果Check(ans)不成立，返回-1。
cur[i][j]记录mid后城市i到城市j之间的灰尘度。
max(mat[i][j]-mid/N*2-(i<mid%N)-(j<mid%N),L[i][j])

代码

核心代码

#include <iostream>
#include <sstream>
#include <vector>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<string>
#include<algorithm>
#include<functional>
#include<queue>
#include <stack>
#include<iomanip>
#include<numeric>
#include <math.h>
#include <climits>
#include<assert.h>
#include<cstring>#include <bitset>
using namespace std;template<class T = int>
vector<T> Read(int n,const char* pFormat = "%d") {vector<T> ret(n);for(int i=0;i<n;i++) {scanf(pFormat, &ret[i]);	}return ret;
}template<class T = int>
vector<T> Read( const char* pFormat = "%d") {int n;scanf("%d", &n);vector<T> ret;T d;while (n--) {scanf(pFormat, &d);ret.emplace_back(d);}return ret;
}string ReadChar(int n) {string str;char ch;while (n--) {do{scanf("%c", &ch);} while (('\n' == ch));str += ch;}return str;
}
template<class T1,class T2>
void ReadTo(pair<T1, T2>& pr) {cin >> pr.first >> pr.second;
}template<class T = int >
class CFloyd
{
public:CFloyd(int n, const T INF = 1000 * 1000 * 1000) :m_INF(INF){m_vMat.assign(n, vector<T>(n, m_INF));for (int i = 0; i < n; i++) {m_vMat[i][i] = 0;}}void SetEdge(int i1, int i2, const T& dis, bool bDirect = false){m_vMat[i1][i2] = min(m_vMat[i1][i2], dis);if (!bDirect) {m_vMat[i2][i1] = m_vMat[i1][i2];}}vector<vector<T>> Dis(){auto vResMat = m_vMat;const int n = m_vMat.size();for (int i = 0; i < n; i++){//通过i中转for (int i1 = 0; i1 < n; i1++){if (m_INF == vResMat[i1][i]){continue;}for (int i2 = 0; i2 < n; i2++){//此时：m_vMat[i1][i2] 表示通过[0,i)中转的最短距离vResMat[i1][i2] = min(vResMat[i1][i2], vResMat[i1][i] + vResMat[i][i2]);//m_vMat[i1][i2] 表示通过[0,i]中转的最短距离}}}return vResMat;};vector<vector<T>> m_vMat;//结果串const T m_INF;
};template<class INDEX_TYPE>
class CBinarySearch
{
public:CBinarySearch(INDEX_TYPE iMinIndex, INDEX_TYPE iMaxIndex) :m_iMin(iMinIndex), m_iMax(iMaxIndex) {}template<class _Pr>INDEX_TYPE FindFrist(_Pr pr){auto left = m_iMin - 1;auto rightInclue = m_iMax;while (rightInclue - left > 1){const auto mid = left + (rightInclue - left) / 2;if (pr(mid)){rightInclue = mid;}else{left = mid;}}return rightInclue;}template<class _Pr>INDEX_TYPE FindEnd(_Pr pr){INDEX_TYPE leftInclude = m_iMin;INDEX_TYPE right = m_iMax + 1;while (right - leftInclude > 1){const auto mid = leftInclude + (right - leftInclude) / 2;if (pr(mid)){leftInclude = mid;}else{right = mid;}}return leftInclude;}
protected:const INDEX_TYPE m_iMin, m_iMax;
};class Solution {
public:int Ans(vector<vector<int>>& mat, vector<vector<int>>& L, int Q) {const int N = mat.size();auto Check = [&](int mid) {auto cur = L;for (int i = 0; i < N; i++)for (int j = 0; j < N; j++) {cur[i][j] = max(cur[i][j], mat[i][j] - mid / N * 2 - (i < mid% N) - (j < mid% N));}CFloyd<int> floyd(N);floyd.m_vMat.swap(cur);auto res = floyd.Dis();long long ans = 0;for (const auto& v : res) {ans += accumulate(v.begin(), v.end(), 0);}return ans <= Q;};auto ans = CBinarySearch<int>(0, 1e7).FindFrist(Check);return Check(ans) ? ans : -1;}};int main() {
#ifdef _DEBUGfreopen("a.in", "r", stdin);
#endif // DEBUGint N,Q;	cin >> N >> Q;vector < vector<int>> mat(N), L(N);for (int i = 0; i < N; i++) {mat[i] = Read<int>(N);}for (int i = 0; i < N; i++) {L[i] = Read<int>(N);}auto res = Solution().Ans(mat, L, Q);cout << res << std::endl;
#ifdef _DEBUG			Out(mat, "mat=");Out(L, "L=");printf(",Q=%d;", Q);
#endif			return 0;
}

单元测试

vector<vector<int>> mat, L;int Q;TEST_METHOD(TestMethod11){mat = { {0,2,4},{2,0,1},{4,1,0} }, L = { {0,2,2},{2,0,0},{2,0,0} }, Q = 10;auto res = Solution().Ans(mat, L, Q);AssertEx(2, res);}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。