第十三届蓝桥杯Java、C++、Python组国赛真题——环境治理（三语言AC）

ゝ一世哀愁。 2023-09-28 23:17 49阅读 0赞

#### 目录 ####

*  1.环境治理
 *   *  1.问题描述
     *  2.输入格式
     *  3.输出格式
     *  4.样例输入
     *  5.样例输出
     *  6.数据范围
     *  7.原题链接
 *  2.解题思路
 *  3.模板代码
 *   *  C++
     *  Java
     *  python

## 1.环境治理 ##

### 1.问题描述 ###

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

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

P = ∑ i = 0 n − 1 ∑ j = 0 n − 1 d ( i , j ) P=\\sum\_\{i=0\}^\{n-1\} \\sum\_\{j=0\}^\{n-1\} d(i, j) P=i=0∑n−1j=0∑n−1d(i,j)

其中  d ( i , j ) d(i, j) d(i,j) 表示城市  i i i 到城市  j j j 之间灰尘度最小的路线对应的灰尘度的值。 为了改善出行环境, 每个城市都要有所作为, 当某个城市进行道路改善时, 会将与这个城市直接相连的所有道路的灰尘度都减少 1 , 但每条道路都有一个 灰尘度的下限值  L L L, 当灰尘度达到道路的下限值时, 无论再怎么改善, 道路的 灰尘度也不会再减小了。

具体的计划是这样的:

第 1 天, 0 号城市对与其直接相连的道路环境进行改善;

第 2 天, 1 号城市对与其直接相连的道路环境进行改善;

⋯ \\cdots ⋯

第  n n n 天,  n − 1 n-1 n−1 号城市对与其直接相连的道路环境进行改善;

第  n + 1 n+1 n\+1 天, 0 号城市对与其直接相连的道路环境进行改善;

第  n + 2 n+2 n\+2 天, 1 号城市对与其直接相连的道路环境进行改善;

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

### 2.输入格式 ###

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

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

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

### 3.输出格式 ###

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

### 4.样例输入 ###

3 10  
0 2 4  
2 0 1  
4 1 0  
0 2 2  
2 0 0  
2 0 0

### 5.样例输出 ###

### 6.数据范围 ###

1 ≤ n ≤ 100 , 0 ≤ L i j ≤ D i j ≤ 100000 , 0 ≤ Q ≤ 2 31 − 1 1≤n≤100,0≤Lij ≤Dij ≤100000,0≤Q≤2^\{31\} −1 1≤n≤100,0≤Lij≤Dij≤100000,0≤Q≤231−1 。

### 7.原题链接 ###

[环境治理][Link 1]

## 2.解题思路 ##

首先，对于求解`P`指的公式，我们要清楚，是每个点到其他所有点的最短路径之和相加，这种涉及到任意两点的最短路，加上  n n n 的最大范围只有`100`，很明显我们需要想到`Floyd`算法求任意两点的最短路。

我们并没有一个直观的算法直接求得答案，所以，我们考虑**二分答案。** 如果改善`x`天是符合要求的，那么大于`x`的天数也一定符合，但小于`x`的天数不一定，所以满足二段性，我们可以二分。

我们用`g[][]`记录初始道路的灰尘度,`m[][]`记录每条道路的最低灰尘度,`f[][]`记录的是在改善`x`天后的每条道路的环境。这样我们就可以使用二分+`Floyd`的做法得到答案。

当然这里有一些需要注意的细节问题，当我们改变`f[i][j]`的值时，相应的也要改变`f[j][i]`的值，因为任意两点只存在一条双向道路，所以这两个状态应该表示的是同一条道路。每次`check`时，别忘记将`f[][]`重置回`g[][]`，再去减去对于的天数。`floyd`函数每次跑完后，计算并返回此时的`P`值。

最开始时我们可以判断每条道路都是最低复杂度的情况下，计算出来的`P`是否大于`Q`，如果大于说明肯定无解，直接返回`-1`即可。二分对于`r`的上限也需要注意，最多`100`个点，每个点最大`1e5`，所以理论上我们只要开到大于`1e7`以上就不会有问题，否则样例过大时可能会出错。

时间复杂度： O ( n 3 l o g ( n ∗ m ) ) O(n^3log(n\*m)) O(n3log(n∗m))

## 3.模板代码 ##

### C++ ###

#include<bits/stdc++.h>
    using namespace std;
    typedef long long LL;
    const int N=110;
    
    LL g[N][N];
    LL m[N][N];
    LL f[N][N];
    LL n,q;
    LL floyd()
    {
        
    	LL a=0;
    	for (int k = 1; k <= n; k ++ )
            for (int i = 1; i <= n; i ++ )
                for (int j = 1; j <= n; j ++ )
                    f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
    
        for(int i=1;i<=n;++i)
        	for(int j=1;j<=n;++j)
        		a+=f[i][j];
        return a;
    }
    //改善X天
    bool check(LL x){
        
    	memcpy(f,g,sizeof(g));
    	LL h=x/n;
    	LL s=x%n;
    	for(int i=1;i<=n;++i){
        
    		for(int j=1;j<=n;++j){
        
    			if(i==j) continue;
    			if(i<=s) f[i][j]=max(m[i][j],f[i][j]-h-1);
    			else f[i][j]=max(m[i][j],f[i][j]-h);
    			f[j][i]=f[i][j];
    		}
    	}
    	return floyd()<=q;
    }
    void solve()
    {
        
    	cin>>n>>q;
    	for(int i=1;i<=n;++i){
        
    		for(int j=1;j<=n;++j){
        
    			cin>>g[i][j];
    		}
    	}
    	for(int i=1;i<=n;++i){
        
    		for(int j=1;j<=n;++j){
        
    			cin>>m[i][j];
    			f[i][j]=m[i][j];
    		}
    	}
    	if(floyd()>q){
        
    		cout<<-1<<endl;
    		return;
    	}
    	LL l=0,r=1000000000;
    	while(l<r){
        
    		int mid=l+r>>1;
    		if(check(mid)) r=mid;
    		else l=mid+1;
    	}
    	cout<<r<<endl;
    }
    int main() 
    {
        
    	solve();
        return 0;
    }

### Java ###

import java.io.*;
    
    public class Main {
        
        static int N=110;
        static long[][] g=new long[N][N],m=new long[N][N],f=new long[N][N];
        static long n,q;
        static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        static PrintWriter  out=new PrintWriter(new OutputStreamWriter(System.out));
        public static void main(String[] args) throws IOException {
        
            String[] s=br.readLine().split(" ");
            n=Long.parseLong(s[0]);
            q=Long.parseLong(s[1]);
            for(int i=1;i<=n;++i){
        
                s=br.readLine().split(" ");
                for(int j=1;j<=n;++j){
        
                    g[i][j]=Long.parseLong(s[j-1]);
                }
            }
            for(int i=1;i<=n;++i){
        
                s=br.readLine().split(" ");
                for(int j=1;j<=n;++j){
        
                    m[i][j]=Long.parseLong(s[j-1]);
                    f[i][j]=m[i][j];
                }
            }
            if(floyd()>q){
        
                out.println(-1);
                out.flush();
                return;
            }
            long l=0,r=1000000000;
            while(l<r){
        
                long mid=l+r>>1;
                if(check(mid)) r=mid;
                else l=mid+1;
            }
            out.println(r);
            out.flush();
        }
        static long floyd(){
        
            long a=0;
            for (int k = 1; k <= n; k ++ )
                for (int i = 1; i <= n; i ++ )
                    for (int j = 1; j <= n; j ++ )
                        f[i][j] =Math.min(f[i][j], f[i][k] + f[k][j]);
    
            for(int i=1;i<=n;++i)
                for(int j=1;j<=n;++j)
                    a+=f[i][j];
            return a;
        }
        static boolean check(long x){
        
            for(int i=1;i<=n;++i){
        
                for(int j=1;j<=n;++j) f[i][j]=g[i][j];
            }
            long h=x/n;
            long s=x%n;
            for(int i=1;i<=n;++i){
        
                for(int j=1;j<=n;++j){
        
                    if(i==j) continue;
                    if(i<=s) f[i][j]=Math.max(m[i][j],f[i][j]-h-1);
                    else f[i][j]=Math.max(m[i][j],f[i][j]-h);
                    f[j][i]=f[i][j];
                }
            }
            return floyd()<=q;
        }
    }

### python ###

import copy
    N=110
    g=[[0]*N for i in range(N)]
    m=[[0]*N for i in range(N)]
    f=[[0]*N for i in range(N)]
    n,q=map(int,input().split())
    def floyd(f):
        a=0
        for k in range(1,n+1):
            for i in range(1,n+1):
                for j in range(1,n+1):
                    f[i][j]=min(f[i][j],f[i][k]+f[k][j])
        for i in range(1,n+1):
            for j in range(1,n+1):
                a=a+f[i][j]
        return a
    def check(x,g):
        f=copy.deepcopy(g)
        h=x//n
        s=x%n
        for i in range(1,n+1):
            for j in range(1,n+1):
                if i==j:
                    continue
                if i<=s:
                    f[i][j]=max(m[i][j],f[i][j]-h-1)
                else:
                    f[i][j]=max(m[i][j],f[i][j]-h)
                f[j][i]=f[i][j]
        return  floyd(f)<=q
    
    def solve():
        for i in range(1,n+1):
            l=list(map(int,input().split()))
            for j in range(1,n+1):
                g[i][j]=l[j-1]#灰尘度
        for i in range(1,n+1):
            l = list(map(int, input().split()))
            for j in range(1,n+1):
                m[i][j]=l[j-1]#灰尘度的下限值
                f[i][j]=m[i][j]
        if floyd(f)>q:
            print(-1)
            return
        l,r=0,10000000
        while (l < r):
            mid=(l+r)>>1
            if (check(mid,g)):
                r=mid
            else:
                l=mid+1
        print(r)
    solve()

[Link 1]: https://www.lanqiao.cn/problems/2178/learning/