[USACO23DEC] Minimum Longest Trip G

Yorg / 2024-10-23 / 原文

算法

简单算法

DAG 上最长路很好实现, 即按照拓扑序 dp

设已经知道最长路答案为 $f_x$
现将每个点按照 $f_x$ 分层, 最小层级没有出边, 显然字典序排名相同
推导下一层时, 对于出边 $(u, v)$ , 按照边权为第一关键字, 上一层的 $v$ 的排名为第二关键字排序, 即可得到字典序最小的最长路

对每一层, 处理完时再排序即可继续推导

代码

#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;
}

这是不难理解的, 用类似于 bfs 的方式转移

总结

对于有多个问的题目, 考虑在解决一个问时的本质, 并从此下手解决问题

稍复杂的通用性算法

转化问题后发现关键问题是怎么求字典序最小
容易想到的是转移过程中记录下字符串, 逐个比较, 复杂度 $O(n^2)$, 无法通过

字符串 hash 可以 $O(\log \left| S \right|)$ 的找到第一个不同的位置, 这很好, 但是在这个题里怎么做呢
转移时, 记录当前转移的字符串 hash 值, 然后在判断时, 二分的查找第一个不同的位置, 进行转移
有种写法是在转移链上倍增, 显然是正确的~~, 并且我其实不知道怎么用二分做~~