BZOJ 4386 Wycieczki

发表于 | 更新于

Link

Solution

为什么大家都一看这道题就是矩阵乘法。。为什么我就从来没听说过。。 不过用矩阵乘法的求法是很好理解的吧 如果边权为11，那就给邻接矩阵的a[0][u]a[0][u]赋值为11，表示以uu为终点，走00步，有一种路径。 矩阵乘一下相当于走了一步，可以看一下矩阵乘法的式子，就是统计方案的DP。 这样的话，二分需要走多少步，然后矩阵快速幂，用方案数目跟KK比较，最后可以得到答案。 然而会T。这样的话，就可以用类似倍增LCA的做法，处理出邻接矩阵的22的kk次方，然后从大到小试乘，如果可以的话就加入答案。 边权不为11，那就把每个点拆成三个，表示边权为1,2,31,2,3的时候所到的点的分身。 因为拆了点，本来有些点是不会成为路径的终点的却可以成为路径的终点，这种方案不能算进去。 于是就在矩阵上乘上这个点的出度，相当于矩阵里是路径的倒数第二个点的方案数目，乘上一个出度才是完整的路径。 所以条件需要是<K< K，最后再Ans++Ans++

另外

本题需要卡常数尽量减少运算+有理有据的底层优化

Tips

矩阵乘法求路径数目？感觉很喵的样子

Code

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
#include "lucida"

const int MAXN=40+11,MAXP=120+11,MAXLOG=63+5;
int64 INF;
int64 add(int64 x,int64 y) {
	return x+y<INF?x+y:INF;
}
int64 mul(int64 x,int64 y) {
	return (x==0) || (y==0) || (x<INF/y)?x*y:INF;
}
struct Square {
	int64 a[MAXP][MAXP];
	int n;
	Square(){}
	Square(int n):n(n) {
		memset(a,0,sizeof(a));
	}
	int64 *operator [](int x) {
		return a[x];
	}
	friend Square operator *(Square &a,Square &b) {
		assert(a.n==b.n);
		static Square res;
		int n=a.n;
		new (&res) Square(n);
		for(int i=0;i<=n;++i)
			for(int k=0;k<=n;++k)
				if(a[i][k]) {
					bool inf=a[i][k]==INF;
					for(int j=0;j<=n;++j)
						if(b[k][j]) {
							if((!inf) && b[k][j]!=INF)
								res[i][j]=add(res[i][j],mul(a[i][k],b[k][j]));
							else
								res[i][j]=INF;
							}
				}
		res.n=n;
		return res;
	}
	Square &operator *=(Square &b) {
		return *this=*this*b;
	}
}f[MAXLOG];
int id[MAXN][3],noc,oud[MAXP];
int64 Count(Square &tran) {
	int64 temp=0;
	for(int i=1;i<=noc;++i) { 
		temp=add(temp,mul(oud[i],tran[0][i]));
	}
	return temp;
}
int main() {
//	freopen("input","r",stdin);
	int n,m;int64 K;
	is>>n>>m>>K;
	INF=K*3;
	new (&f[0]) Square(n*3);
	for(int i=1;i<=n;++i) { 
		for(int d=0;d<=2;++d)
			id[i][d]=++noc;
		f[0][0][id[i][0]]=f[0][id[i][0]][id[i][1]]=f[0][id[i][1]][id[i][2]]=1;
	}
	f[0][0][0]=1;
	for(int i=1;i<=m;++i) {
		int u,v,c;
		is>>u>>v>>c;
		oud[id[u][c-1]]++;
		f[0][id[u][c-1]][id[v][0]]++;
	}
	int log2=0;
	while((1ll<<(log2+1))<=INF)
		log2++;
	for(int i=1;i<=log2;++i)
		f[i]=f[i-1]*f[i-1];
	int64 Ans=0;
	Square cur(n*3),temp;
	cur[0][0]=1;
	for(int lg=log2;~lg;--lg) {
		temp=cur*f[lg];
		if(Count(temp)<K) {
			Ans|=(1ll<<lg);
			cur=temp;
		}
	}
	++Ans;
	os<<(Ans<=INF?Ans:-1)<<'\n';
	return 0;
}