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

题目

问题描述

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 \leq Q$ 。请问最少要经过多少天之后, $P$ 指标可以满足 $P \leq Q$ 。如果在初始时就已经满足条件, 则输出 0 ; 如果永远不可能满足, 则输出 $-1$ 。

输入格式

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

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

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

输出格式

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

样例输入

样例输出

评测用例规模与约定

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

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

对于所有评测用例, $1 \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算法

思路

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

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

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

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

算减少量：根据题意，如果当前已经过了 $d$ 天（以下提到的城市的编号为 $1 \sim n$ ）：

城市 $1 \sim d \bmod n$ 的道路环境会被改善 $\frac{d}{n} + 1$ 次。
城市 $d \bmod n + 1 \sim n$ 的道路环境会被改善 $\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);
    }
}

目录CONTENT

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

题目

解题

方法一：Floyd算法

思路

代码

评论区