P11744 Dynamic TSP Problem

Mr_Az · 2025-02-16 08:48:09 · 题解

P11744 Dynamic TSP Problem

Algorithm:

二分。

好像爆标了？

Solution:

观察到答案具有单调性（你带的钱越多获利的次数越多剩的钱也越多），因此考虑二分答案。

考虑最显然的 \text{O}(nm\log V)，遍历每一条路径判断合法性。

观察到 n 和 m 的大小差距十分的大，所以 m 条路径有许多是重复遍历到的。因此我们可以考虑把每一条路径拿 vector 存下来，每次 check 只需要从 n 个点出发，记录起点，当前资金，获利次数，每次走到一个点 u 就查询所有起点到 u 的路径，检查合法性。

每次 check 时间复杂度 \text{O}(n^2)，总的时间复杂度 \text{O}(n^2\log V)。

Code:

namespace Mr_Az{
    const int N=508,M=2e5+8;
    int T=1;
    int n,m;
    vector<int> e[N];
    struct city{int a,b,c;}a[N];
    struct ask{int y,k;};
    vector<ask> journey[N][N];
    inline bool dfs(int u,int fa,int st,int x,int hl){
        if(x>=a[u].a) x+=a[u].b,hl++;
        else x-=a[u].c;
        if(journey[st][u].size()) for(auto [c,d]:journey[st][u]) if(x<c||hl<d) return 0;
        for(auto v:e[u]) if(v!=fa) if(!dfs(v,u,st,x,hl)) return 0;
        return 1;
    }// u: 当前节点 st: 起点 x: 当前资金 hl: 获利次数
    inline bool check(int x){
        for(rint i=1;i<=n;i++) if(!dfs(i,0,i,x,0)) return 0;
        return 1;
    }
    inline void solve(){
        read(n,m);
        for(rint i=1,u,v;i<n;i++) read(u,v),e[u].pb(v),e[v].pb(u);
        for(rint i=1,A,B,C;i<=n;i++) read(A,B,C),a[i]={A,B,C};
        for(rint i=1,A,B,C,D;i<=m;i++) read(A,B,C,D),journey[A][B].pb({C,D});
        // 由于 n 只有 500，所以直接开个 vector 把所有的旅行记录下来
        int l=0,r=INF,ans=0;
        while(l<r){
            int mid=l+r>>1;
            if(check(mid)) r=mid;
            else l=mid+1;
        }// 二分答案
        printf("%lld\n",l);
    }
    inline void mian(){if(!T) read(T);while(T--) solve();}
}