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

1.环境治理

1.问题描述

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

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

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

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

具体的计划是这样的:

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

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

$\cdots$

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

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

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

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

2.输入格式

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

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

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

3.输出格式

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

4.样例输入

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

5.样例输出

2

6.数据范围

$1\le n\le 100,0\le Lij\le Dij\le 100000,0\le Q\le 2^{31}-1$ 。

7.原题链接

环境治理

2.解题思路

首先，对于求解P指的公式，我们要清楚，是每个点到其他所有点的最短路径之和相加，这种涉及到任意两点的最短路，加上 $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}log(n\ast m))$

3.模板代码

C++

#include
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

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()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54