• https://www.luogu.com.cn/problem/P1954

第一问显然可以 dag dp，求出每个点的真实最晚发车时间，
然后用这个东西贪心构造。

第二问还是用同一个 dp 数组，不过这次贪心构造的时候，我们忽略所有询问点传递闭包里的节点。

#include <lastweapon/io>
using namespace lastweapon;

const int N = int(2e3)+9;

VI adj[N], rdj[N]; int f[N], k[N], o[N];
bool vis[N];
int n, m;


void dfs(int u = 0) {
    vis[u] = 1; f[u] = k[u];
    for (auto v: adj[u]) {
        if (!vis[v]) dfs(v);
        checkMin(f[u], (f[v] ? f[v] : k[v]) - 1);
    }
}

void rfs(int u = 0) {
    vis[u] = 1; f[u] = 0;
    for (auto v: rdj[u])  {
        if (!vis[v]) rfs(v);
    }
}

int main() {

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    RD(n, m); REP(i, n) RD(k[i]);

    DO(m) {
        int a, b; RD(a, b), a--, b--;
        adj[a].PB(b);
        rdj[b].PB(a);
    }
    REP(i, n) if (!vis[i]) dfs(i); REP(i, n) o[i] = i;

    sort(o, o+n, [](int a, int b) {
         return f[a] < f[b];
    });

    REP(i, n) printf("%d ", o[i]+1); puts("");

    REP(i, n) {
        RST(vis); rfs(i); REP(i, n) if (!vis[i]) dfs(i);

        sort(o, o+n, [](int a, int b) {
            return f[a] > f[b];
        });

        int m = n-1; RST(vis);

        REP(ii, n) {
            int i = o[ii]; if (!f[i]) break;
            int t = min(m, f[i]);
            while (vis[t]) --t; vis[t] = 1;
            while (vis[m]) --m;
        }
        printf("%d ", m+1);
    }
}

Posted by xiaodao
Category: 日常