侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

【Floyd算法, 二分查找】环境治理

GabrielxD
2023-03-16 / 0 评论 / 0 点赞 / 242 阅读 / 1,852 字
温馨提示:
本文最后更新于 2023-03-16,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

环境治理 - 蓝桥云课


问题描述

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

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

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

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

具体的计划是这样的:

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

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

\cdots

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

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

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

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

输入格式

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

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

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

输出格式

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

样例输入

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

样例输出

2

评测用例规模与约定

对于 30%30 \% 的评测用例, 1n100LijDij101 \leq n \leq 10 , 0 \leq L_{i j} \leq D_{i j} \leq 10

对于 60%60 \% 的评测用例, 1n500LijDij1000001 \leq n \leq 50 , 0 \leq L_{i j} \leq D_{i j} \leq 100000 ;

对于所有评测用例, 1n100,0LijDij100000,0Q23111 \leq n \leq 100,0 \leq L_{i j} \leq D_{i j} \leq 100000,0 \leq Q \leq 2^{31}-1

运行限制

  • 最大运行时间:10s
  • 最大运行内存: 512M

解题

方法一:Floyd算法

思路

根据 PP 指标的定义:所有点到所有点的 最短距离 的和,可以看出本题本质上是多源最短路问题,要用到 Floyd算法

如果暴力来做的话天数最小可能是 00 ,最大可能是 max(DijLij)×n\max(D_{ij} - L_{ij}) \times n ,那么最坏就需要枚举 DD 次才能找到答案,再加上 Floyd 算法的时间复杂度,即使本题时限有 10s10s ,也只能过 60%60\% 的数据。

但是我们发现,随着天数的增加道路环境只会慢慢改善,也就是说 PP 指标会随着天数的增加单调递减,具有单调性就可以用二分查找了,求最少的天数也就是要二分下界

接下来考虑如何实现 check() 函数:我们二分的是天数,那么就需要根据天数来算出每条路径的灰尘的 减少量 ,然后用所有路径的灰尘度减去其减少量去初始化 distsdists 数组,再进行 Floyd 算法,最后双层枚举所有城市算出最短路总和即得到 PP 指标,返回 PPQQ 比较的结果。

算减少量:根据题意,如果当前已经过了 dd 天( 以下提到的城市的编号为 1n1 \sim n ):

  • 城市 1dmodn1 \sim d \bmod n 的道路环境会被改善 dn+1\frac{d}{n} + 1 次。
  • 城市 dmodn+1nd \bmod n + 1 \sim n 的道路环境会被改善 dn\frac{d}{n} 次。

代码

import java.util.*;
import java.io.*;

public class Main {
    static final int INF = 0x3f3f3f3f;
    static int n, q;
    static int[][] g, lim, dists;

    static void floyd() {
        for (int k = 1; k <= n; ++k) {
            for (int i = 1; i <= n; ++i) {
                for (int j = 1; j <= n; ++j) {
                    dists[i][j] = Math.min(dists[i][j], dists[i][k] + dists[k][j]);
                }
            }
        }
    }

    static boolean check(int m) {
        for (int i = 1; i <= n; ++i) dists[i] = g[i].clone();
        int a = m / n, b = m % n;
        for (int i = 1; i <= n; ++i) {
            int rdc1 = a + (i <= b ? 1 : 0);
            for (int j = i + 1; j <= n; ++j) {
                int rdc2 = a + (j <= b ? 1 : 0);
                dists[i][j] = dists[j][i] = Math.max(g[i][j] - rdc1 - rdc2, lim[i][j]);
            }
        }
        floyd();
        int p = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if ((p += dists[i][j]) > q) return false;
            }
        }
        return p <= q;
    }

    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        n = (int) in.nval;
        in.nextToken();
        q = (int) in.nval;
        g = new int[n + 1][n + 1];
        lim = new int[n + 1][n + 1];
        dists = new int[n + 1][n + 1];
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                in.nextToken();
                g[i][j] = g[j][i] = (int) in.nval;
            }
        }
        int mx = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                in.nextToken();
                lim[i][j] = lim[j][i] = (int) in.nval;
                mx = Math.max(mx, Math.abs(g[i][j] - lim[i][j]));
            }
        }
        int l = 0, r = mx * n;
        while (l < r) {
            int m = l + (r - l >> 1);
            if (check(m)) r = m;
            else l = m + 1;
        }
        System.out.println(check(l) ? l : -1);
    }
}
0
博主关闭了所有页面的评论