2023美国建模比赛Y题
时间: 2023-09-17 11:09:36 浏览: 48
题目描述:
某个城市的交通系统由 $N$ 个交叉口和 $M$ 条道路组成。每个交叉口可以连接多条道路,但是两个交叉口之间最多只能连接一条道路。
为了方便起见,我们把每个交叉口标号为 $1,\cdots,N$,每条道路标号为 $1,\cdots,M$。每条道路都是双向的,连接两个不同的交叉口。从交叉口 $i$ 出发可以经过任意数量的道路到达交叉口 $j$。我们定义 $d_{i,j}$ 表示从交叉口 $i$ 到交叉口 $j$ 的最短路的长度。
我们定义「交叉口 $i$ 的距离」为所有 $d_{i,j}$ 的和,其中 $j\ne i$。现在,我们希望移除某些道路,使得任意两个交叉口之间的最短路长度不超过 $L$。请问在这种情况下,所有交叉口的距离之和最小是多少?
请你计算所有交叉口的距离之和的最小值。
输入格式:
第一行包含三个整数 $N$、$M$ 和 $L$。
接下来 $M$ 行,每行两个整数 $u,v$,表示一条连接交叉口 $u$ 和 $v$ 的道路。
输出格式:
输出所有交叉口的距离之和的最小值。
数据范围:
对于 $20\%$ 的数据,$1\leq N\leq 10^2$,$1\leq M\leq 10^3$。
对于 $60\%$ 的数据,$1\leq N\leq 10^3$,$1\leq M\leq 10^4$。
对于 $100\%$ 的数据,$1\leq N\leq 10^4$,$1\leq M\leq 10^5$,$1\leq L\leq 10^9$,保证给定图是连通的。
输入样例1:
4 4 10
1 2
2 3
2 4
3 4
输出样例1:
20
输入样例2:
4 4 7
1 2
2 3
2 4
3 4
输出样例2:
12
提示:
样例1中,将第 2 条道路移除后,任意两个交叉口之间的最短路长度均不超过 $10$。
样例2中,将第 1 条和第 4 条道路移除后,任意两个交叉口之间的最短路长度均不超过 $7$。