HDU 6343 - Problem L. Graph Theory Homework - [(伪装成图论题的)简单数学题]

时间：2022-10-09 16:29:50

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6343

Time Limit: 2000/1000 MS (Java/Others)　　Memory Limit: 262144/262144 K (Java/Others)

Problem Description
There is a complete graph containing n vertices, the weight of the i-th vertex is wi.
The length of edge between vertex i and j (i≠j) is ⌊sqrt(|wi−wj|)⌋.
Calculate the length of the shortest path from 1 to n.

Input
The first line of the input contains an integer T (1≤T≤10) denoting the number of test cases.
Each test case starts with an integer n (1≤n≤10^5) denoting the number of vertices in the graph.
The second line contains n integers, the i-th integer denotes wi (1≤wi≤10^5).

Output
For each test case, print an integer denoting the length of the shortest path from 1 to n.

Sample Input
1
3
1 3 5

Sample Output
2

 

题意：

给出一张完全图由n个点组成，编号1~n，每个点有一个权重 ${w_i }$，对于任意不同两点 i 和 j 之间的边的长度为 $\left\lfloor {\sqrt {\left| {w_i - w_j } \right|} } \right\rfloor$，

要求给出从1到n的最短路长度。

题解：

先说结论：对于任意两点 i 和 j，${\mathop{\rm edge}\nolimits} \left( {i,j} \right)$ 这条边是最短路；

我们首先来证明：

$\left\lfloor {\sqrt a } \right\rfloor + \left\lfloor {\sqrt b } \right\rfloor \ge \left\lfloor {\sqrt {a + b} } \right\rfloor$

其中 $a,b$ 均为正整数。

证明：

设有两个正整数 $m,n$ 满足 $a \in \left[ {m^2 ,\left( {m + 1} \right)^2 - 1} \right],b \in \left[ {n^2 ,\left( {n + 1} \right)^2 - 1} \right]$，则 $\left\lfloor {\sqrt a } \right\rfloor = m,\left\lfloor {\sqrt b } \right\rfloor = n$，

那么自然就有

$a + b \in \left[ {m^2 + n^2 ,m^2 + n^2 + 2m + 2n} \right]$

$\sqrt {a + b} \in \left[ {\sqrt {m^2 + n^2 } ,\sqrt {m^2 + n^2 + 2m + 2n} } \right]$

此时，我们考察两个完全平方数 $\left( {m + n} \right)^2 ,\left( {m + n + 1} \right)^2$，将他们展开：$m^2 + n^2 + 2mn\;\;,\;\;m^2 + n^2 + 2mn + 2m + 2n + 1$，

显然 $\left( {m + n + 1} \right)^2 = \;m^2 + n^2 + 2mn + 2m + 2n + 1 > m^2 + n^2 + 2m + 2n$，也就是说平方数 $\left( {m + n + 1} \right)^2$ 大于 $a+b$ 所属区间的右端点，

再分类讨论 $\left( {m + n} \right)^2$ 与 $a+b$ 所属区间的右端点的关系：

①若 $mn \ge m + n$，则

$\left( {m + n} \right)^2 = m^2 + n^2 + 2mn \ge m^2 + n^2 + 2m + 2n$

$m + n \ge \sqrt {m^2 + n^2 + 2m + 2n}$

　即

$\left\lfloor {\sqrt a } \right\rfloor + \left\lfloor {\sqrt b } \right\rfloor \ge \sqrt {m^2 + n^2 + 2m + 2n} \ge \sqrt {a + b} \ge \left\lfloor {\sqrt {a + b} } \right\rfloor$

②若 $mn < m + n$，则

$m^2 + n^2 + 2mn < m^2 + n^2 + 2m + 2n$

　也就是说，$a + b$ 所属区间 $\left[ {m^2 + n^2 ,m^2 + n^2 + 2m + 2n} \right]$ 的右端点在两个完全平方数 $\left( {m + n} \right)^2 ,\left( {m + n + 1} \right)^2$ 之间，

　那么根据开根号再向下取整的性质，显然有

$\left\lfloor {\sqrt {a + b} } \right\rfloor \le \sqrt {\left( {m + n} \right)^2 } = m + n = \left\lfloor {\sqrt a } \right\rfloor + \left\lfloor {\sqrt b } \right\rfloor$

综上所述，就证明了 $\left\lfloor {\sqrt a } \right\rfloor + \left\lfloor {\sqrt b } \right\rfloor \ge \left\lfloor {\sqrt {a + b} } \right\rfloor$，

而且不难发现，将 $a,b$ 范围扩大成均为非负整数也不会影响上述不等式成立。

接下来，对于完全图上的任意两点 i 和 j，若任取其他一个点 k，我们来证明 $\left\lfloor {\sqrt {\left| {w_i - w_k } \right|} } \right\rfloor + \left\lfloor {\sqrt {\left| {w_k - w_j } \right|} } \right\rfloor \ge \left\lfloor {\sqrt {\left| {w_i - w_j } \right|} } \right\rfloor$，

换句话说，我们要证明 ${\mathop{\rm edge}\nolimits} \left( {i,k} \right) + {\mathop{\rm edge}\nolimits} \left( {k,j} \right) \ge {\mathop{\rm edge}\nolimits} \left( {i,j} \right)$，此处 ${\mathop{\rm edge}\nolimits} \left( {i,j} \right)$ 代表连接 i 和 j 两点的边的长度。

证明：

首先，根据绝对值不等式可以知道

$\left| {w_i - w_k } \right| + \left| {w_k - w_j } \right| \ge \left| {w_i - w_k + w_k - w_j } \right| = \left| {w_i - w_j } \right|$

其次，易知若两非负整数满足 $m \ge n$，则 $\left\lfloor {\sqrt m } \right\rfloor \ge \left\lfloor {\sqrt n } \right\rfloor$，

那么自然就有

$\left\lfloor {\sqrt {\left| {w_i - w_k } \right| + \left| {w_k - w_j } \right|} } \right\rfloor \ge \left\lfloor {\sqrt {\left| {w_i - w_j } \right|} } \right\rfloor$

再者，根据上文证明的公式 $\left\lfloor {\sqrt a } \right\rfloor + \left\lfloor {\sqrt b } \right\rfloor \ge \left\lfloor {\sqrt {a + b} } \right\rfloor$，有

$\left\lfloor {\sqrt {\left| {w_i - w_k } \right|} } \right\rfloor + \left\lfloor {\sqrt {\left| {w_k - w_j } \right|} } \right\rfloor \ge \left\lfloor {\sqrt {\left| {w_i - w_k } \right| + \left| {w_k - w_j } \right|} } \right\rfloor$

最后，上面两个不等式连起来即

$\left\lfloor {\sqrt {\left| {w_i - w_k } \right|} } \right\rfloor + \left\lfloor {\sqrt {\left| {w_k - w_j } \right|} } \right\rfloor \ge \left\lfloor {\sqrt {\left| {w_i - w_j } \right|} } \right\rfloor$

证毕。

那么，我们就知道了图上任意两点 i 和 j，不会有第三个点 k 存在，使得 ${\mathop{\rm edge}\nolimits} \left( {i,k} \right) + {\mathop{\rm edge}\nolimits} \left( {k,j} \right)$ 比 ${\mathop{\rm edge}\nolimits} \left( {i,j} \right)$ 更小，

那么同样不会存在其他两个点 k 和 p，使得 ${\mathop{\rm edge}\nolimits} \left( {i,k} \right) + {\mathop{\rm edge}\nolimits} \left( {k,p} \right) + {\mathop{\rm edge}\nolimits} \left( {p,j} \right)$ 比 ${\mathop{\rm edge}\nolimits} \left( {i,j} \right)$ 更小，

原因很简单，因为 ${\mathop{\rm edge}\nolimits} \left( {k,p} \right) + {\mathop{\rm edge}\nolimits} \left( {p,j} \right) \ge {\mathop{\rm edge}\nolimits} \left( {k,j} \right)$ 且 ${\mathop{\rm edge}\nolimits} \left( {i,k} \right) + {\mathop{\rm edge}\nolimits} \left( {k,j} \right) \ge {\mathop{\rm edge}\nolimits} \left( {i,j} \right)$，

所以，对于任意两点 i 和 j，不管另取多少个点，都不会让从 i 到 j 的路径比 ${\mathop{\rm edge}\nolimits} \left( {i,j} \right)$ 更短，因而 ${\mathop{\rm edge}\nolimits} \left( {i,j} \right)$ 这条边就是最短路。

AC代码：

#include<bits/stdc++.h>

using namespace std;

int main()

{

    int T,n;

    cin>>T;

    while(T--)

    {

        scanf("%d",&n);

        int w,a,b;

        for(int i=;i<=n;i++)

        {

            scanf("%d",&w);

            if(i==) a=w;

            if(i==n) b=w;

        }

        printf("%d\n",(int)floor(sqrt(abs(a-b))));

    }

}

相关文章