魔法
$C$ 国由 $n$ 座城市与 $m$ 条有向道路组成,城市与道路都从 $1$ 开始编号,经过 $i$ 号道路需要 $t_i$ 的费用。
现在你要从 $1$ 号城市出发去 $n$ 号城市,你可以施展最多 $K$ 次魔法,使得通过下一条道路时,需要的费用变为原来的相反数,即费用从 $t_i$ 变为 $−t_i$。
请你算一算,你至少要花费多少费用才能完成这次旅程。
注意:使用魔法只是改变一次的花费,而不改变一条道路自身的 $t_i$;
最终的费用可以为负,并且一个城市可以经过多次(包括 $n$ 号城市)。
输入格式
第一行三个整数 $n,m,K$,表示城市数、道路数、魔法次数限制。
接下来 $m$ 行每行三个整数 $u_i,v_i,t_i$,第 $i$ 行描述 $i$ 号道路,表示一条从 $u_i$ 到 $v_i$ 的有向道路,经过它需要花费 $t_i$。
输出格式
仅一行一个整数表示答案。
数据范围
对于所有测试点和样例满足:
$1 \leq n \leq 100,1 \leq m \leq 2500,0 \leq K \leq {10}^{6},1 \leq u_i,v_i \leq n,1 \leq t_i \leq {10}^{9}$
数据保证图中无自环,无重边,至少存在一条从 $1$ 号城市到达 $n$ 号城市的路径。
每个测试点的具体限制见下表。
测试点编号 | $n \leq$ | $m \leq$ | $K \leq$ | 特殊限制 |
$1 \sim 2$ | $5$ | $20$ | $0$ | 无 |
$3 \sim 4$ | $10$ | $20$ | $50$ | 无 |
$5 \sim 6$ | $10$ | $20$ | $0$ | 无 |
$7 \sim 8$ | $20$ | $200$ | $50$ | 图中无环 |
$9 \sim 10$ | $20$ | $200$ | $0$ | 无 |
$11 \sim 12$ | $100$ | $200$ | $50$ | 图中无环 |
$13 \sim 14$ | $100$ | $200$ | $50$ | 无 |
$15 \sim 18$ | $100$ | $2500$ | $1000$ | 无 |
$19 \sim 20$ | $100$ | $2500$ | ${10}^6$ | 无 |
输入样例1:
4 3 2 1 2 5 2 3 4 3 4 1
输出样例1:
-8
样例1解释
依次经过 $1$ 号道路、$2$ 号道路、$3$ 号道路,并在经过 $1$、$2$ 号道路前使用魔法。
输入样例2:
2 2 2 1 2 10 2 1 1
输出样例2:
-19
样例2解释
依次经过 $1$ 号道路、$2$ 号道路、$1$ 号道路,并在两次经过 $1$ 号道路前都使用魔法。
解题思路
$n$最大取值为$100$,又是求最短路的问题,这提示我们可以往Floyd的方向去想。
定义状态$f(k,i,j)$表示所有从$i$走到$j$最多使用$k$次魔法的方案的集合,属性就是最短距离。根据从$i$到$j$的路径中所经过的点$u$来把路径分成两段,其中前面一段$i \to \cdots \to u$使用魔法次数不超过$k-1$次,后面一段$u \to \cdots \to j$使用魔法次数不超过$1$次,这样就得到状态转移方程$$f(k,i,j) = \min_{1 \leq u \leq n} \{ f(k-1,i,u) + f(1,u,j) \}$$
直接这样做的话时间复杂度为$O(k \cdot n^3)$,肯定会超时。注意到状态转移方程中只涉及到$\min$与$+$运算,具有结合律的性质,可以用类似于快速幂求矩阵乘法的做法来求$f(k,i,j)$。具体请参考这篇博客:min 与 + 运算转换成类似于矩阵乘法的推导过程。
与上面博客的思路一样,我们把$f(k,i,j)$看成是矩阵$F^{k}_{n \times n}$第$i$行第$j$的元素,因此上面的状态转移方程就变成了$$F^{k}_{i,j} = \min_{1 \leq u \leq n}\left\{ F^{k-1}_{i,u} + F^{1}_{u,j} \right\}$$
其中$F^k$是一个$n \times n$的矩阵,里面的每一个元素$F^{k}_{i,j}$表示从$i$到$j$使用魔法不超过$k$次的最短路径。矩阵间的运算就是$F^{k} = F^{k-1} \ F^{1}$,通过递推可以发现有$F^k = \left( F^1 \right)^k$。由于具有结合律,因此可以用快速幂来解决。
那么$F^1$怎么求呢?根据定义矩阵$F^1$中任意一个元素$F^{1}_{i,j}$表示$i$到$j$使用魔法不超过$1$次的最短路径。这里有种暴力的解决方法,就是先求出任意两点间不使用魔法的最短路径,也就是$F^0$,这个直接跑Floyd就可以了。然后再枚举每一条边,把这条边的权值取相反数,假设这条边原来的权值为$w_{u,v}$,那么对于任意两点$i$和$j$,强行走这条边$i \to \cdots \to u \to v \to \cdots \to j$,这条路径就对$w_{u,v}$使用了一次魔法,看看路径长度是否比不使用魔法要短就可以了。因此有$$F^{1}_{i,j} = \min \left\{ F^{0}_{i,j}, \ F^{0}_{i,u} -w_{u,v} + F^{0}_{v,j} \right\}$$
AC代码如下,时间复杂度为$O(n^3 \cdot \log{k})$:
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 typedef long long LL; 5 6 const int N = 110, M = 2510, INF = 0x3f3f3f3f; 7 8 int n, m, k; 9 LL f[N][N], g[N][N], tmp[N][N]; 10 struct Node { 11 int v, w, wt; 12 }e[M]; 13 14 void mul(LL c[][N], LL a[][N], LL b[][N]) { 15 memset(tmp, 0x3f, sizeof(tmp)); 16 for (int i = 1; i <= n; i++) { 17 for (int j = 1; j <= n; j++) { 18 for (int k = 1; k <= n; k++) { 19 tmp[i][j] = min(tmp[i][j], a[i][k] + b[k][j]); 20 } 21 } 22 } 23 memcpy(c, tmp, sizeof(tmp)); 24 } 25 26 int main() { 27 scanf("%d %d %d", &n, &m, &k); 28 for (int i = 1; i <= n; i++) { 29 for (int j = 1; j <= n; j++) { 30 g[i][j] = INF; 31 } 32 g[i][i] = 0; 33 } 34 for (int i = 0; i < m; i++) { 35 int v, w, wt; 36 scanf("%d %d %d", &v, &w, &wt); 37 e[i] = {v, w, wt}; 38 g[v][w] = wt; 39 } 40 // 一开始跑Floyd,得到的g就是F^0 41 for (int k = 1; k <= n; k++) { 42 for (int i = 1; i <= n; i++) { 43 for (int j = 1; j <= n; j++) { 44 g[i][j] = min(g[i][j], g[i][k] + g[k][j]); 45 } 46 } 47 } 48 memcpy(f, g, sizeof(g)); 49 // 求F^1 50 for (int k = 0; k < m; k++) { 51 for (int i = 1; i <= n; i++) { 52 for (int j = 1; j <= n; j++) { 53 f[i][j] = min(f[i][j], g[i][e[k].v] + g[e[k].w][j] - e[k].wt); 54 } 55 } 56 } 57 // 求(F^1)^k 58 while (k) { 59 if (k & 1) mul(g, g, f); 60 mul(f, f, f); 61 k >>= 1; 62 } 63 printf("%lld", g[1][n]); 64 65 return 0; 66 }
参考资料
AcWing 1426. 魔法(蓝桥杯集训·每日一题):https://www.acwing.com/video/4677/