自动搬运

查看原文

来自洛谷，原作者为

	rainygame There is no trap so deadly as the trap you set for yourself.

搬运于2025-08-24 23:11:25，当前版本为作者最后更新于2025-03-21 22:52:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一道很好的 meet-in-middle 题。

首先看到这个乘法，那么大概率就和值域 $V$ 有关了，但是“最多只经过 $O(\log V)$ 条边权不为 $1$ 的边”貌似没有什么用。观察到 $n$ 很小，小到 $O(n\sqrt V)$ 都是可以接受的。那么可以考虑把路径分成两段边权不超过 $\sqrt V$ 的部分，分别处理，最后再枚举中间连接的边统计答案，这就有了一个 meet-in-middle 的壳子。

考虑统计的是 $u\rightarrow v$ 这条边，边权为 $w$。那么应该需要维护两个信息：$f_{i,j}$ 表示是否有一条 $1\rightarrow i$ 的路径边权积为 $j$；$g_{i,j}$ 表示所有 $i\rightarrow n$ 的边权积为 $j$ 的路径中，可以接受的 $1\sim i$ 的最大边权积。求出 $f$ 和 $g$ 只有，对 $f_u$ 和 $g_v$ 双指针一下就可以更新答案了。

$f$ 是好求的。考虑在反图上求出 $g$，对于反图上的一条边 $u\rightarrow v$，可以用 $\min\{\lfloor\dfrac{g_{u,j}}{w}\rfloor,p_v\}$ 更新 $g_{v,jw}$。需要类似 Dijkstra 的转移才能保证正确性，注意优先队列是从大到小排。

时间复杂度为 $O(n\sqrt V\log m)$，平衡一下可以做到 $O(n\sqrt{V\log m})$，但是我懒。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN 105
#define MAXK 32005

int t, n, m; int p[MAXN];
bool f[MAXN][MAXK], vis[MAXN][MAXK]; int h[MAXN][MAXK];
vector<pair<int, int>> e[MAXN], g[MAXN];

struct Node{int u, st, d; bool operator<(Node b)const{return d < b.d;}};

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    for (cin >> t; t; --t){
        cin >> n >> m; for (int i(1); i<=n; ++i) cin >> p[i];
        for (int u, v, w; m; --m) cin >> u >> v >> w, e[u].push_back({v, w}), g[v].push_back({u, w});
        queue<pair<int, int>> que; que.push({1, 1}); f[1][1] = 1;
        while (que.size()){
            int u(que.front().first), st(que.front().second); que.pop();
            for (auto i: e[u]){
                int v(i.first), w(i.second); if (w*st<=min(MAXK-1ll, p[v]) && !f[v][w*st]) f[v][w*st] = 1, que.push({v, w*st});
            }
        }
        priority_queue<Node> pq; pq.push({n, 1, h[n][1]=p[n]});
        while (pq.size()){
            int u(pq.top().u), st(pq.top().st); pq.pop(); if (vis[u][st]) continue; vis[u][st] = 1;
            for (auto i: g[u]){
                int v(i.first), w(i.second);
                if (w*st < MAXK && min(p[v], h[u][st]/w) > h[v][st*w]){
                    pq.push({v, st*w, h[v][st*w]=min(p[v], h[u][st]/w)});
                }
            }
        }
        int ans(-1);
        for (int i(1); i<=n; ++i) for (auto j: e[i]){
            int v(j.first), w(j.second);
            for (int x(1), y(MAXK-1); x<MAXK; ++x){
                for (; y && h[v][y] < w*x; --y); if (y && f[i][x]) ans = max(ans, y*w*x);
            }
        }
        cout << (n == 1 && ans == -1 ? 1 : ans) << '\n';
        for (int i(1); i<=n; ++i){
            for (int j(1); j<MAXK; ++j) vis[i][j] = f[i][j] = h[i][j] = 0;
            e[i].clear(); e[i].shrink_to_fit(); g[i].clear(); g[i].shrink_to_fit();
        }
    }

    return 0;
}