BZOJ4386[POI2015]Wycieczki / Luogu3597[POI2015]WYC

Solution

想到边权为$1$的情况直接矩乘就可以得出长度$<=t$ 的路径条数，然后二分check一下即可

但是拓展到边权为$2$，$3$ 时，需要新建节点 $i+n$ 和 $i+2n$. 从 $i+n$ 到 $i$ 连边， $i+2n$ 到 $i+n$ 连边

若 $dis[j,i]=2$，则把 $j$ 向 $i+n$连边，距离为 $3$时同理

但是发现这样点数就有 $3*N$ 个，二分答案+矩乘的复杂度会非常高。

那么只能用和倍增求 $LCA$ 类似的解法，二进制枚举

复杂度为$O(N^3 logk)$

Code

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define rd read()
 5 #define ll long long
 6 #define N 130
 7 #define R register
 8 using namespace std;
 9 
10 int n, up, m;
11 ll cnt;
12 
13 int read() {
14     int X = 0, p = 1; char c = getchar();
15     for (; c > '9' || c < '0'; c = getchar())
16         if (c == '-') p = -1;
17     for (; c >= '0' && c <= '9'; c = getchar())
18         X = X * 10 + c - '0';
19     return X * p;
20 }
21 
22 struct matrix {
23     ll mp[N][N];
24     bool yue;
25     matrix() {
26         yue = false;
27     }
28     matrix operator * (const matrix &b) const {
29         matrix re;
30         memset(re.mp, 0, sizeof(re.mp));
31         for (R int i = 0; i <= up; ++i)
32             for (R int j = 0; j <= up; ++j) {
33                 for (R int k = 0; k <= up; ++k)
34                     re.mp[i][j] += mp[i][k] * b.mp[k][j];
35                 if (re.mp[i][j] < 0) re.yue = true;
36             }
37         return re;
38     }
39 }ans, po[70];
40 
41 bool check(matrix tmp) {
42     ll rest = cnt;
43     if (tmp.yue) return 1;
44     for (int i = 1; i <= n; ++i) {
45         if (tmp.mp[i][0] < 0) return 1;
46         if (tmp.mp[i][0] - 1 >= rest) return 1;
47         rest -= tmp.mp[i][0] - 1;
48     }
49     return 0;
50 }
51 
52 int main()
53 {
54     n = rd; m = rd;
55     up = n * 3;
56     scanf("%lld", &cnt);
57     po[0].mp[0][0] = 1;
58     for (int i = 1; i <= n; ++i) {
59         po[0].mp[i + n][i] = 1;
60         po[0].mp[i + 2 * n][i + n] = 1;
61         po[0].mp[i][0] = 1;
62         ans.mp[i][i] = 1;
63     }
64     for (R int i = 1; i <= m; ++i) {
65         int u = rd, v = rd, w = rd - 1;
66         po[0].mp[u][v + n * w]++;
67     }
68     bool flag = false;
69     int lim;
70     for (lim = 1; lim <= 65; ++lim) {
71         po[lim] = po[lim - 1] * po[lim - 1];
72         if (check(po[lim])) {
73             flag = true; break;
74         }
75     }
76     if (!flag ) return puts("-1"), 0;
77     ll res = 0;
78     for (int i = lim; ~i; --i) {
79         matrix tmp = ans * po[i];
80         if (!check(tmp)) ans = tmp, res += 1LL << i;
81     }
82     printf("%lld
", res);
83 }

View Code