Minimum Longest Trip

0000pnc · 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;
}