自动搬运

查看原文

来自洛谷，原作者为

	0000pnc 几人仍眼睛明亮 几人已失了魂

搬运于2025-08-24 22:53:36，当前版本为作者最后更新于2023-12-16 23:33:00，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

感觉大家都在写倍增 hash。但是有一个简单的方法。

题意：给出一个 DAG，边有标签且长度均为 $1$，对于每个结点，求：

• 从这个点出发的最长路长度。
• 最长路中，边的标签组成的序列字典序最小的路径的标签之和。

首先对于最长路，可以按照拓扑序 dp，这是容易的。

然后考虑第二问怎么做。设已经得到的结点 $x$ 第一问答案为 $f_{x}$。

我们考虑这个拓扑序 dp 的过程，其本质就是在结点 $u$ 的各个出边中，寻找最优的答案。

那么我们有以下想法：如果我们能够求出 $f_{u}=k$ 的结点中字典序最小的最长路的排名，那么在递推 $f_{u}=k+1$ 的点的答案时可以直接使用出边 $\{w,v\}$ 中 $w$ 最小且 $v$ 的排名尽量靠前的。然后所有 $f_{u}=k+1$ 的推完再 sort 一下就可以知道新的排名（代码里是用的 priority_queue，二者无区别）。那么第二问就做完了。

时间复杂度 $\mathcal{O}(m+n\log n)$。

#include <bits/stdc++.h>
using namespace std;

struct edge {
	int to, w;
};
int n, m, tot, cnt, tp[200005], siz[200005], dep[200005], rk[200005], id[200005];
long long ans[200005];
vector<edge> v[200005], v2[200005];
struct res {
	int e, rnk, to;
};

bool operator< (res x, res y) {
	if (x.e < y.e) return true;
	else if (x.e > y.e) return false;
	return x.rnk > y.rnk;
}
bool cmp(int x, int y) { return dep[x] < dep[y]; }

void topo() {
	queue<int> q;
	for (int i = 1; i <= n; i++) {
		if (!siz[i]) q.push(i);
	}
	while (!q.empty()) {
		int x = q.front(); q.pop();
		tp[++tot] = x;
		for (auto tmp : v2[x]) {
			if (siz[tmp.to]) {
				siz[tmp.to]--;
				if (!siz[tmp.to]) q.push(tmp.to);
			}
		}
	}
}

void dp() {
	for (int i = 1; i <= n; i++) {
		int x = tp[i];
		for (auto tmp : v2[x]) {
			dep[tmp.to] = max(dep[tmp.to], dep[x] + 1);
		}
	}
	for (int i = 1; i <= n; i++) id[i] = i;
	sort(id + 1, id + n + 1, cmp);
}

void bfs() {
	topo(); dp();
	priority_queue<res> pq;
	int mxdep = 0;
	for (int i = 1; i <= n; i++) {
		int x = id[i];
		if (dep[x] != mxdep) {
			mxdep = dep[x];
			while (!pq.empty()) {
				auto tmp = pq.top(); pq.pop();
				rk[tmp.to] = ++cnt;
			}
		}
		if (dep[x]) {
			int mn = 0x3f3f3f3f, mx = 0;
			for (auto tmp : v[x]) {
				if (dep[tmp.to] == dep[x] - 1) mn = min(mn, tmp.w);
			}
			for (auto tmp : v[x]) {
				if (dep[tmp.to] == dep[x] - 1 && tmp.w == mn) mx = max(mx, rk[tmp.to]);
			}
			for (auto tmp : v[x]) {
				if (dep[tmp.to] == dep[x] - 1 && tmp.w == mn && rk[tmp.to] == mx) {
					ans[x] = ans[tmp.to] + tmp.w;
					pq.push({tmp.w, rk[tmp.to], x});
					break;
				}
			}
		}
		else pq.push({0, 0, x});
	}
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 1, x, y, w; i <= m; i++) {
		scanf("%d %d %d", &x, &y, &w);
		v[x].push_back({y, w}); siz[x]++;
		v2[y].push_back({x, w});
	}
	bfs();
	for (int i = 1; i <= n; i++) printf("%d %lld\n", dep[i], ans[i]);
	return 0;
}