OI - 魔法(洛谷) | Lucky_Glass's Blog

以心为名，名为爱惜

0%

OI - 魔法(洛谷)

发表于 更新于 分类于 Valine：

看来入门组的题也能暴露出一些问题

（不要问我为什么把矩阵构造出来然后没有写矩阵加速……→_→）

# 题面

> 洛谷 P6190

点击展开/折叠题面

C 国由 $n$ 座城市与 $m$ 条有向道路组成，城市与道路都从 $1$ 开始编号，经过 $i$ 号道路需要 $t_i$ 的费用。

现在你要从 $1$ 号城市出发去 $n$ 号城市，你可以施展最多 $k$ 次魔法，使得通过下一条道路时，需要的费用变为原来的相反数，即费用从 $t_i$​ 变为 $-t_i$。请你算一算，你至少要花费多少费用才能完成这次旅程。

注意：使用魔法只是改变一次的花费，而不改变一条道路自身的 $t_i$；最终的费用可以为负，并且一个城市可以经过多次（包括 $n$ 号城市）。

# 解析

根据最优性，下面这种情况不可能发生：

从一个点出发不使用魔法然后回到这个点

所以定义状态 $p_{t,i}$，表示用了 $t$ 次魔法后到达 $i$ 点的最小花费。把所有 $kn$ 个状态建点，转移建有向边，由于之前证明的结论，这是一个 DAG，更具体地说，这是一个分层图，$t$ 相同的状态在同一层。

（本来想默认大家都知道DP转移的……）点击展开/折叠递推式

设原图上两点间距离为 $d_{i,j}$，边集为 $E$，$(a,b)$ 代表 $a,b$ 两点间的边权（如果有边）。

$$p_{t,i}=\min\{p_{t-1,j}+\min_{(j,k)\in E}(d_{k,i}-(i,j))\}$$

然后我们发现对于指定的 $i,j$，上式后面那一堆 $\min$ 是可以预处理的，所以记预处理后 $\min\limits_{(j,k)\in E}(d_{k,i}-(i,j))$ 值为 $tran_{i,j}$。

这样的话，分层图中状态 $p_{t-1,j}$ 就会向 $p_{t,j}$ 连一条权为 $tran_{i,j}$ 的边。而我们发现相邻两层图之间的边的形式是完全一样的，那么能不能矩阵快速幂优化？

构造出 $n\times n$ 矩阵 $M$：$M_{i,j}=tran_{i,j}$，以及初始 $n\times 1$ 矩阵 $T^0$：$T^0_{i,1}=p_{0,i}=d_{1,i}$。然后重新定义矩阵乘法：原本矩阵乘法是一行一列对应位置相乘后相加，而我们希望能够有 $M\times T^0=T^1$（$T^1_{i,1}=p_{1,i}$），则应该修改为“一行一列对应项相加后取 min”。

能否矩阵快速幂取决于是否满足交换律、分配律、结合律。

  • 显然加法和 min 分别满足交换律；
  • 加法满足结合律，又有 $\min\{\min\{a,b\},c\}=\min\{a,\min\{b,c\}\}$，min也满足结合律；
  • 有 $\min\{a,b\}+c=\min\{a+c,b+c\}$，满足分配律（注意到这里的加法相当于“乘法”，优先级高于 min）

于是直接矩阵快速幂即可。但是注意到我们不一定直接用完 $k$ 次魔法，可能你无法用完 $k$ 次，于是不能简单地 $T^0\times(M)^k=T^k$，然后取 $p_{k,n}=T^k_{n,1}$。那么就要矩阵额外维护一行记录 $\min\limits_{t=1\to n}p_{t,n}$。

# 源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
/*Lucky_Glass*/
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=105,M=1e6+10;

int n,m,lim;
long long inf;
long long dis[N][N],tran[N][N],f[2][N],len[N][N];

struct MATRIX{
	long long mat[N][N];
	int n,m;
	MATRIX(int x,int y){n=x,m=y;}
	MATRIX(){}
	MATRIX operator *(const MATRIX &B){
		MATRIX res(n,B.m);
		for(int i=1;i<=n;i++)
			for(int j=1;j<=B.m;j++){
				long long tmp=inf;
				for(int k=1;k<=m;k++)
					if(mat[i][k]!=inf && B.mat[k][j]!=inf)
						tmp=min(tmp,mat[i][k]+B.mat[k][j]);
				res.mat[i][j]=tmp;
			}
		return res;
	}
	void PerInit(int siz){
		n=m=siz;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				mat[i][j]=i==j? 0:inf;
	}
}Tran,Res,One;

MATRIX Pow(MATRIX A,int b){
	MATRIX B;B.PerInit(A.n);
	while(b){
		if(b&1) B=B*A;
		A=A*A;
		b>>=1;
	}
	return B;
}

inline int Ri(){
	register int a=0,c=getchar();
	while(c<'0' || '9'<c) c=getchar();
	while('0'<=c && c<='9') a=(a<<1)+(a<<3)+c-'0',c=getchar();
	return a;
}
void Dijkstra(int s){
	priority_queue< pair<long long,int> > que;
	bool fix[N]={};
	que.push(make_pair(0,s));
	dis[s][s]=0;
	while(!que.empty()){
		int u=que.top().second;que.pop();
		if(fix[u]) continue;
		fix[u]=true;
		for(int v=1;v<=n;v++)
			if(dis[s][v]>dis[s][u]+len[u][v])
				dis[s][v]=dis[s][u]+len[u][v],que.push(make_pair(-dis[s][v],v));
	}
}
int main(){
	n=Ri(),m=Ri(),lim=Ri();
	memset(dis,0x3f,sizeof dis),inf=dis[0][0];
	memset(len,0x3f,sizeof len);
	for(int i=1;i<=m;i++){
		int u=Ri(),v=Ri(),l=Ri();
		len[u][v]=min(len[u][v],1ll*l);
	}
	for(int i=1;i<=n;i++) Dijkstra(i);
	memset(tran,0x3f,sizeof tran);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++){
			if(len[j][i]!=inf) tran[i][j]=-len[j][i];
			for(int k=1;k<=n;k++)
				if(len[j][k]!=inf && dis[k][i]!=inf)
					tran[i][j]=min(tran[i][j],dis[k][i]-len[j][k]);
		}
	memset(f,0x3f,sizeof f);
	for(int i=1;i<=n;i++) f[0][i]=dis[1][i];
	Tran.n=Tran.m=n+1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)
			Tran.mat[i][j]=tran[i][j];
		Tran.mat[i][n+1]=inf;
	}
	for(int i=1;i<n;i++) Tran.mat[n+1][i]=inf;
	Tran.mat[n+1][n]=Tran.mat[n+1][n+1]=0;
	One.n=n+1,One.m=1;
	for(int i=1;i<=n;i++)
		One.mat[i][1]=dis[1][i];
	One.mat[n+1][1]=dis[1][n];
	One=Pow(Tran,lim+1)*One;
	printf("%lld\n",One.mat[n+1][1]);
	return 0;
}

THE END

Thanks for reading!