P7831 [CCO 2021] Travelling Merchant 的题解

这是一种神秘的贪心优化 DP trick。

设点

u

的答案为

dp_u

，对于相邻点

v

，有方程：

dp_u = \displaystyle\min_{v}\max\{r_{u,v},dp_v - p_{u,v}\}

可以发现这是一类 DP 方程带环的问题。

换一种思路，考虑对每一个

dp_u

的值设计一个上界，借此断掉其中的环，然后通过朴素的拓扑排序精确到确切值。

考虑到在行走的整个过程中，我们的资产是不降的。或者说，观察转移方程，

dp_u \le r_{max}

总成立。也就是说，对于一个

r_{max}

我们可以使用它直接转移此边，回顾拓扑排序的内涵，这条边完成了其连接两点间的转移，也就完成了它在拓扑排序中的任务，可以删去。

考虑拓扑排序的过程，处理掉环之外的部分后，发现实质上当前任意一点均可以到达一个环。假设当前全局

r_{max}

所在边为

u\rarr v

，此时设

dp_u

上界为

r_{max}

必然保证其可以在整个图上任意一边顺利通行，也就必然可以到达一个环，故此时的操作合法。此时一条边已经被断掉，多出了部分 DAG，继续使用拓扑排序正常转移掉非环部分。然后继续查找全局

r_{max}

，重复过程。

我们发现这样的算法能够计算到所有点，且完美处理的 DP 转移带环的问题。时间复杂度

\mathcal{O}(m\log m + n + m)

，相当优秀。

总体来说，这个 trick 就是通过题目中的一些全局信息，确定局部 DP 上界，断掉环之后可继续转移，遇到环再断，最终将答案精确到确切数值。

好题好题。

代码

CPP

#include<bits/stdc++.h>
#define endl '\n'
//#define MSOD


using namespace std;
using ll = long long;

constexpr ll N = 2e5 + 5;

bool vis[N];
ll n, m;
ll in[N], ans[N];
struct E {
	ll u, v, r, p, id;
	inline friend bool operator < (E x, E y) {
		return x.r > y.r;
	}
} edg[N];
struct T {
	ll v, r, p, id;
	T(ll x, ll y, ll z, ll w) : v(x), r(y), p(z), id(w) {}
	
};
vector<T> g[N];
inline void solve() {
	cin>>n>>m;
	for(int i = 1 ; i <= m ; i ++) {
		cin>>edg[i].u>>edg[i].v>>edg[i].r>>edg[i].p;
		edg[i].id = i;
		g[edg[i].v].push_back(T(edg[i].u, edg[i].r, edg[i].p, edg[i].id));
		in[edg[i].u] ++;
	}
	sort(edg + 1, edg + m + 1);
	fill(ans + 1, ans + n + 1, LLONG_MAX);
	queue<ll> q;
	for(int i = 1 ; i <= n ; i ++) {
		if(!in[i]) {
			q.push(i);
		}
	}
	for(int i = 1 ; i <= m ; i ++) {
		while(!q.empty()) {
			ll u = q.front();
			q.pop();
			for(auto i : g[u]) {
				ll v = i.v, r = i.r, p = i.p, id = i.id;
				if(vis[id]) {
					continue;
				}
				vis[id] = true;
				if(ans[u] != LLONG_MAX) {
					ans[v] = min(ans[v], max(ans[u] - p, r));
				}
				if((-- in[v]) == 0) {
					q.push(v);
				}
			}
		}
		if(!vis[edg[i].id]) {
			vis[edg[i].id] = true;
			ans[edg[i].u] = min(ans[edg[i].u], edg[i].r);
			if((-- in[edg[i].u]) == 0) {
				q.push(edg[i].u);
			}
		}
	}
	for(int i = 1 ; i <= n ; i ++) {
		cout<<(ans[i] == LLONG_MAX ? -1 : ans[i])<<" \n"[i == n];
	}
	return;
}

signed main() {
	ios::sync_with_stdio(false), cout.tie(0), cin.tie(0);
	int TC = 1;
#ifdef MSOD
	cin>>TC;
#endif
	while(TC --) {
		solve();
	}
	return 0;
}

P7831 [CCO 2021] Travelling Merchant 的题解

文章操作

相关推荐

评论

P7831 [CCO 2021] Travelling Merchant 的题解