自动搬运

查看原文

来自洛谷，原作者为

	Mr_Az 我的尸体不会腐烂在泥土里，我会像鸟儿一样死在天空中。

搬运于2025-08-24 23:09:54，当前版本为作者最后更新于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();}
}